01背包题解

分析思路：（这题Markdown稀烂）首先这是个背包问题，并且是01背包，意味着每件货物至多只能取一次。但关键还在输出，要求出箱子的最小剩余空间，也就是需要重量最大且不超过背包容量。容易发现，这题可以转化为$v=w$（此处$v$指价值，不是容量）的背包，重量即价值！然后剩下的就是背包问题模板了，套一下动态转移方程即可。空间优化版时间复杂度$O(n*V)$，空间复杂度$O(V)$。

#include<iostream>
using namespace std;
int n,v,w[20005],dp[20005];
int main(){
    cin>>v>>n;
    for(int i=1;i<=n;i++) cin>>w[i];
    for(int i=1;i<=n;i++){
        for(int j=v;j>=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+w[i]);//模板我就不讲了
    }
    cout<<v-dp[v];//注意状态表示（容量-最大价值or重量）
    return 0;
}