官方题解｜火星背包 II

题目解析

本道题目不难想到套用经典的「01背包问题」，定义 $\tt{dp[i][j]}$ 为前 $i$ 个物品，背包容量为 $j$ 可以获取的最大价值，然后使用 $\tt{dp[i][j] = \max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])}$ 进行转移。
此种做法只能够拿到一部分分数（约 $40\%$），无法通过本题，原因是本题背包的容量和物品的重量都特别大 $(1 \le w_i \le M \le 10^9)$。使用上述方式解决这道题目的时间复杂度为 $\mathrm{O}(NM)$。

但本题 $N$ 以及 $v_i$ 的值都比较小，我们不妨将定义更改为 $\tt{dp[i][j]}$ 为前 $i$ 个物品获取价值为 $j$ 所需要的最小重量，然后使用 $\tt{dp[i][j] = \min(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i])}$ 进行转移。由于 $j \le \sum_{i=1}^{N}v_i$，此方法的复杂度为 $\mathrm{O}(N \times \sum_{i=1}^{N}v_i)$，在本题的数据范围下完全可以通过。

AC代码

#include <bits/stdc++.h>

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    std::cin >> n >> m;
    std::vector<int> w(n), v(n);
    for (int i = 0; i < n; ++i)
        std::cin >> w[i] >> v[i];
    const int V = std::accumulate(v.begin(), v.end(), 0LL);
    std::vector<int> dp(V + 1, m + 1);
    dp[0] = 0;
    for (int i = 0; i < n; ++i)
        for (int j = V; j >= v[i]; --j)
            dp[j] = std::min(dp[j], dp[j - v[i]] + w[i]);
    int res = 0;
    for (int i = 1; i <= V; ++i)
        if (dp[i] <= m) res = i;
    std::cout << res << '\n';
    return 0;
}