首页 > 代码库 > 装箱问题
装箱问题
8785:装箱问题
总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
-
有一个箱子容量为V(正整数,0<=v<=20000),同时有n个物品(0< n<n<=30),每个物品有一个体积(正整数)。< n<="" p="">
要求n个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。
- 输入
- 第一行是一个整数V,表示箱子容量。
第二行是一个整数n,表示物品数。
接下来n行,每行一个正整数(不超过10000),分别表示这n个物品的各自体积。 - 输出
- 一个整数,表示箱子剩余空间。
- 样例输入
-
24 6 8 3 12 7 9 7
- 样例输出
-
0
- 来源
- NOIP2001复赛 普及组 第四题
- 【思路】是取若干个物品 不是每个物品取若干个;
- 先01背包求f[V]不超过V体积能放物品体积的最大值
- 再求V-f[V]‘
- 【代码】
-
#include<iostream> #include<cstdio> #include<cstring> 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; }
装箱问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。