2280 - 啦啦啦装箱问题
时间限制 : 1 秒
内存限制 : 128 MB
有一个箱子容量为V(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，每个物品有一个体积 (正整数)。要求从 n 个物品中，任取若千个装入箱内，使箱子的剩余空间为最小。
题目输入
第一行，一个整数，表示箱子容量；
第二行，一个整数，表示有n个物品；
接下来n行，分别表示这n个物品的各自体积。
题目输出
一个整数，表示箱子剩余空间。
输入/输出样例
输入格式
24 6 8 3 12 7 9 7
输出格式
0
C++解答
#include<cstdio> int f[20001],a[40],v,n,i,j; main(){ scanf("%d%d",&v,&n); for(i=1;i<=n;i++)scanf("%d",&a[i]); for(i=1;i<=v;i++)f[i]=0; f[0]=1; for(i=1;i<=n;i++)for(j=v;j>=a[i];j--) if(f[j]==0)if(f[j-a[i]]==1)f[j]=1; for(i=v;i>=0;i--)if(f[i]==1)break; printf("%d\n",v-i);}