【9906】装箱问题

Time Limit: 10 second
Memory Limit: 2 MB

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

Input

箱子的容量v 物品数n 接下来n行，分别表示这n个物品的体积

Output

箱子剩余空间

Sample Input

24
6
8
3
12
7
9
7

Sample Output

0

Sample Input1

90
12
3
7
4
5
13
2
8
4
7
6
5
7

Sample Output1

19

【题解】

这是将背包作为工具的问题。

先用背包求出这些物品可以达到哪些容积值。

这点可以用一个bool 型的can[]数组来得到。

因为每个物品都只能拿一次，所以用0/1背包的更新方式，即倒序。

for (j = maxv->w[i])

if (can[j-w[i])

can[j] = true;

然后初值can[0] = true;其他can值都为false;

最后从maxv逆序到一个最大的k，can[k]==true;

然后输出maxv-k就可以了

【代码】

#include <cstdio>
#include <cstring>

int v,n,w[31];
bool can[20010];

void input_data()
{
	scanf("%d",&v);
	scanf("%d",&n);
	for (int i = 1;i <= n;i++) //输入这些物品的体积 
		scanf("%d",&w[i]);	
}

void get_ans()
{
	memset(can,false,sizeof(can));
	can[0] = true; //一开始什么都不放就可以达到0体积了 
	for (int i = 1;i <= n;i++)
		for (int j = v;j >= w[i];j--) // 按照0/1背包的更新方式就能得到其它可以达到的数值了 
			if (can[j-w[i]])
				can[j] = true;	
	for (int i = v;i >= 0;i--) //然后逆序获得一个最大值。 
		if (can[i])
			{
				printf("%d",v-i); //输出maxv减去这个值。就可以啦 
				return;
			}
}

int main()
{
	//freopen("F:\rush.txt","r",stdin);
	input_data();
	get_ans();
	return 0;
}