首页 > 代码库 > tyvj p1016 装箱问题
tyvj p1016 装箱问题
装箱问题From admin
描述 Description
有一个箱子容量为v(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，
每个物品有一个体积 (正整数)。
要求从 n 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
输入格式 InputFormat
第一行，一个整数，表示箱子容量；
第二行，一个整数，表示有n个物品；
接下来n行，分别表示这n个物品的各自体积。
输出格式 OutputFormat
一个整数，表示箱子剩余空间。
简单DP 01背包
#include<stdio.h>#include<string.h>#include<math.h>#include<iostream>#include<algorithm>#include<queue>#include<stack>#define mem(a,b) memset(a,b,sizeof(a))#define ll __int64#define MAXN 1000#define INF 0x7ffffff#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;int dp[30000];int num[50];int main(){ int n,m,i,j,k; int maxx=0; mem(dp,0); scanf("%d%d",&m,&n); dp[0]=1; for(i=1;i<=n;i++) scanf("%d",&num[i]); for(i=1;i<=n;i++) for(j=m;j>=num[i];j--) if(j-num[i]>=0&&dp[j-num[i]]==1) { dp[j]=1; if(j>maxx) maxx=j; } cout<<m-maxx<<endl; return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。