题解 | 装箱问题

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int V,n;
    cin>>V>>n;
    vector<int> volumn(n,0);
    for(int i=0;i<n;i++){
        cin>>volumn[i];
    }
    //首先，构造dp[i]表示，存在一些物品的体积使得总体积为i
    vector<bool> dp(V+1,false);
    dp[0]=true;
    for(int i=0;i<n;i++){
        int v=volumn[i];
        for(int j=V;j>=v;j--){
            if(dp[j-v]==true){//如果dp[j-v]能填充，那再加这次的v，dp[j]依然可以填充
                dp[j]=true;
            }
        }
    }
    //计算出最大能装
    int maxVolumn=0;
    for(int i=V;i>=0;i--){
        if(dp[i]){
            maxVolumn=i;
            break;
        }
    }
    cout<<V-maxVolumn;
    return 0;
}
// 64 位输出请用 printf("%lld")