luogu1049装箱问题
装箱问题
一个箱子容量为V//容量
同时有n个物品//n个 体积&&价值
要求n个物品中任取若干个装入箱内，使箱子的剩余空间为最小// v减去价值最大 */
#include<iostream> #include<cstdio> using namespace std; int n,v; int w[21000]; int a[21000]; int main(){ cin>>v>>n; for(int i=1;i<=n;++i) scanf("%d",&w[i]); for(int i=1;i<=n;++i){ for(int j=v;j>=w[i];j--){ a[j]=max(a[j],a[j-w[i]]+w[i]); } } cout<<v-a[v]; return 0; }
投递腾讯等公司10个岗位 >
