题解 | #装箱问题#

解题思路：

• 典型的01背包，转换结果为$V-d{p}_{V}V-dp\_V$,求$d{p}_{V}dp\_V$的最大值即可。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int V, n;
    ios::sync_with_stdio(false);
    cin>>V>>n;
    vector<int> v(n+1);
    for(int i = 1; i <= n; ++i)
        cin>>v[i];
    vector<int> dp(V+1);
    for(int i = 1; i <= n; ++i){
        for(int j = V; j >= v[i]; --j){
            dp[j] = max(dp[j], dp[j-v[i]] + v[i]);
        }
    }
    cout<<V-dp[V]<<endl;
    return 0;
}