01背包问题。
与模板不同，这道题要求的是最小剩余空间，也就是求背包里最多能放多少东西。
所以状态转移方程变为 fi= fi - w[i] + wi 。
其中 fi 表示当背包容量为 i 时可放的最大重量。
注意要倒着循环。
#include<bits/stdc++.h> using namespace std; int f[20001],a[31],n,v; int main() { scanf("%d%d",&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-a[i]]+a[i],f[j]); } } cout<<v-f[v]<<endl; return 0; }
原文：https://www.cnblogs.com/ying-xue/p/zhuang-xiang-wen-ti.html