火星背包 II｜反向背包问题

第三题 - 火星背包 II

题目链接跳转：点击跳转

一道反向 $0/1$ 背包的模板题目。通常，$0/1$ 背包问题的目标是选择若干物品，使得这些物品的总重量不超过背包容量，并且这些物品的总价值最大化。而反向 $0/1$ 背包问题则是反其道而行之，其目标是选择若干物品，使得这些物品的总重量不低于给定的最小值，并且这些物品的总价值最小化。

主要就是状态的定义比较难：设 $dp[j]$ 表示恰好凑出总重量为 $j$ 的最小代价。那么我们可以得到如下的状态转移方程：

$$dp_j = \min(dp_j, dp_{j-w_i} + v_i);$$

根据状态的定义，我们将 $dp$ 数组一开始全部初始化为正无穷大，同时另 $dp_0 = 0$，表示恰好凑出重量为 $0$ 的物品的最小代价为 $0$，正无穷大代表暂时还没有答案，需要在后续的循环中更新。

之后就是跑一遍正常的 Knapsack 01 代码就好了。在输出答案的时候，我们需要找到一个满足条件 $(dp[i] \le m)$​ 的最大值。用一个 for 循环就可以搞定了。

本题的 AC 代码如下：

#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;

/*
反向 01 背包题目。
问题不大，X03 的同学们在集训营做过类似的题目（maybe 仅限杭州八月一期）。
*/

int n, m, sum;
int dp[100005], ans;
int w[1005], v[1005];

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i=1; i<=n; i++){
        cin >> w[i] >> v[i];
        sum += v[i];
    }
    memset(dp, 0x7f, sizeof dp);
    dp[0] = 0;
    for (int i=1; i<=n; i++){
        for (int j=sum; j>=v[i]; j--){
            dp[j] = min(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    for (int i=1; i<=sum; i++){
        if (dp[i] <= m) ans = i;
    }
    cout << ans << endl;
    return 0;
}