CodeVS/1014

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	失误原因（初次提交分数）
装箱问题	★☆☆☆☆	答案正确	100	2014/11/04 19:48:55	算法错误（0）

题意

经典问题，又称0-1背包问题。

题解

最经典的DP了没什么好说的。第一次一手滑居然交成完全背包。

代码

1014.cpp代码已折叠 展开折叠内容
#include<cstdio> #include<algorithm> int v,n,vi[50],Ans; bool u[30000]={1}; int main() { scanf("%d%d",&v,&n); for(int i=1;i<=n;++i) scanf("%d",&vi[i]); for(int i=1;i<=n;++i) for(int j=v;j>=vi[i];--j) { if(u[j-vi[i]]&&!u[j]) { u[j]=1; Ans=std::max(Ans,j); } } printf("%d",v-Ans); return 0; }