A79 装箱问题 题解

洛谷 P1049 [NOIP 2001 普及组] 装箱问题

思路

考虑使用 0/1 背包解题。

虽然标准 0/1 背包需要价值和重量，但题目中只有重量，所以可以将输入的值同时当成价值以及重量。

因此，状态转移方程如下：

dp[j] = max(dp[j], dp[j-w[i]] + v[i]);

注意：由于题目要求输出剩余空间，所以输出的是v-dp[v]而不是dp[v]。

完整代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int v,n; cin>>v>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    
    vector<int> dp(v+1);
    for(int i=1;i<=n;i++){
        for(int j=v;j>=a[i];j--){ // 使用一维 dp 数组所以倒序枚举
            dp[j] = max(dp[j],dp[j-a[i]]+a[i]);
        }
    }
    cout<<v-dp[v];
    
    return 0;
}