题解 | [NOIP2001]装箱问题

#include <bits/stdc++.h>

using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0);

//const int N=;

int main()
{
    IOS
    int v, n;
    cin>>v>>n;
    vector<int> w(n+1), dp(v+1);
    int res=0;
    dp[0]=1;
    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--)
            if(dp[j-w[i]]) dp[j]=dp[j-w[i]], res=max(res, j);
    cout<<v-res;
    return 0;
}

01背包变题，加了个背景，然后物品的体积同时也代表物品的价值

还是让dp[0]是合法的，遍历后若成功更新，res记录最大物品占用容量，然后v-res即为所求

#牛客春招刷题训练营#