解题思路:

  • 典型的01背包,转换结果为VdpVV-dp_V,求dpVdp_V的最大值即可。
dpj=max(dpj,dpjvi+vi)dp_j = \max(dp_j, dp_{j-v_i}+v_i)
#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;
}