试题 算法训练 装箱问题

资源限制

在成都网站建设、做网站过程中，需要针对客户的行业特点、产品特性、目标受众和市场情况进行定位分析，以确定网站的风格、色彩、版式、交互等方面的设计方向。创新互联还需要根据客户的需求进行功能模块的开发和设计，包括内容管理、前台展示、用户权限管理、数据统计和安全保护等功能。

内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s

问题描述

有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）。
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

---

输入格式

第一行为一个整数，表示箱子容量；
第二行为一个整数，表示有n个物品；
接下来n行，每行一个整数表示这n个物品的各自体积。

输出格式

一个整数，表示箱子剩余空间。

---

样例输入

24 6 
8 3 12 7 9 7

样例输出

0

代码–我自己的纯代码–纯模拟–但可以过

#include#include 
using namespace std;
const int V = 2e4+5;
const int N = 30+5;
int a[N], v, n, book[V], flag[V];
int main()
{int m = 0;
	cin >>v >>n;
	for (int i = 1; i<= n; i++)cin >>a[i];
	sort(a + 1, a + 1 + n);//排序
	book[0] = 1;//初始化
	for (int i = 1; i<= n; i++)
	{if (a[i] >v)break;//如果单个数据就已经大于V了就可以退出了
		for (int j = 0; j<= v; j++)
		{//第一	是存在的数
            //第二	新的数要在范围内
            //第三	不能是这次循环里才出现的数
            //第四	新出现的数不能是标记过的数
			if (book[j] == 1 && j + a[i]<= v && flag[j] == 0 && book[j + a[i]] == 0)
			{		book[j + a[i]] = 1;//标记已经出现过
				flag[j + a[i]] = 1;//标记这是新出现的数
				if (m< j + a[i])m = j + a[i];//取大值
			}
		}
		for (int j = 0; j<= v; j++)flag[j] = 0;//去除标记
		if (m == v)break;//如果已经达到V了也可以退出了
	}
	cout<< v - m;
	return 0;
}

大佬代码–动态规划–1维背包

#includeusing namespace std;
inline int max(int a, int b) {return a >b ? a : b; }
int v, n;//v为箱子容量 , n个物品
int dp[20003];//箱子容量为i时，可装入的大值
int a[33];
int main()
{cin >>v >>n;
	for (int i = 1; i<= n; i++)
		cin >>a[i];
	for (int i = 1; i<= n; i++)
		for (int j = v; j >= a[i]; j--)
			dp[j] = max(dp[j - a[i]] + a[i], dp[j]);
	cout<< v - dp[v];
	return 0;
}

再写写二维背包

#includeusing namespace std;
inline int max(int a, int b) {return a >b ? a : b; }
int v, n;//v为箱子容量 , n个物品
int dp[33][20003];
int a[33];
int main()
{cin >>v >>n;
	for (int i = 1; i<= n; i++)cin >>a[i];
	for (int i = 1; i<= n; i++)
		for (int j = 0; j<= v; j++)
		{//放的下，取大值
			if(j>=a[i])
				dp[i][j] = max(dp[i - 1][j - a[i]] + a[i], dp[i - 1][j]);
			else
				dp[i][j] = dp[i - 1][j];//放不下，直接就等于上一轮
		}
	cout<< v - dp[n][v];
	return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

本文标题：试题算法训练装箱问题-创新互联
标题网址：http://csdahua.cn/article/gscjd.html