P1049 装箱问题
题目描述
有一个箱子容量为VV（正整数，0 le V le 200000≤V≤20000），同时有nn个物品（0<n le 300<n≤30，每个物品有一个体积（正整数）。
要求nn个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
输入输出格式
输入格式：
11个整数，表示箱子容量
11个整数，表示有nn个物品
接下来nn行，分别表示这nn个物品的各自体积
输出格式：
11个整数，表示箱子剩余空间。
输入输出样例
说明
NOIp2001普及组 第4题
#include<bits/stdc++.h> using namespace std; int a[50]; int f[20005]; int main(){ int v,n; cin>>v>>n; for(int i=1;i<=n;++i){ scanf("%d",a+i); } for(int i=1;i<=n;++i) for(int j=v;j>=a[i];--j) f[j]=max(f[j],f[j-a[i]]+a[i]); cout<<v-f[v]; }