8785:装箱问题
总时间限制:
- 1000ms 内存限制:
- 65536kB
- 描述
-
有一个箱子容量为V（正整数，0<=v<=20000），同时有n个物品（0< n<n<=30），每个物品有一个体积（正整数）。< n<="" p="">
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
输入 - 第一行是一个整数V，表示箱子容量。 第二行是一个整数n，表示物品数。 接下来n行，每行一个正整数（不超过10000），分别表示这n个物品的各自体积。 输出
- 一个整数，表示箱子剩余空间。 样例输入
-
2468312797
样例输出 -
0
来源 - NOIP2001复赛 普及组 第四题
- 【思路】是取若干个物品 不是每个物品取若干个；
- 先01背包求f[V]不超过V体积能放物品体积的最大值
- 再求V-f[V]'
- 【代码】
-
#include
#include #include using namespace std;int v[50],f[21000];int main(){ int V,n; scanf("%d%d",&V,&n); for(int i=1;i<=n;i++) scanf("%d",&v[i]); for(int i=1;i<=n;i++) { for(int k=V;k>=v[i];k--) { f[k]=max(f[k],f[k-v[i]]+v[i]); } } printf("%d",V-f[V]); return 0;}