有一个箱子容量为VVV（正整数，0≤V≤200000 \le V \le 200000≤V≤20000），同时有nnn个物品（0<n≤300<n \le 300<n≤30，每个物品有一个体积（正整数）。
要求nnn个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
111个整数，表示箱子容量
111个整数，表示有nnn个物品
接下来nnn行，分别表示这nnn个物品的各自体积
111个整数，表示箱子剩余空间。
24 6 8 3 12 7 9 7
0
没啥好说的，本质上就是dp求解使得允许条件下背包能装的体积最大。注意最后要用v减去dp[v]得到剩余空间。
#include <bits/stdc++.h> using namespace std; int v,n; int dp[20005]={0}; int obj[34]={0}; int main() { int i,j; cin>>v>>n; for(i=1;i<=n;i++) { scanf("%d",&obj[i]); } for(i=1;i<=n;i++) { for(j=v;j>=obj[i];j--) { dp[j]=max(dp[j],dp[j-obj[i]]+obj[i]); } } cout<<v-dp[v]; return 0; }
原文：https://www.cnblogs.com/lipoicyclic/p/12343556.html