题解 | #【模板】01背包#

【模板】01背包

https://www.nowcoder.com/practice/fd55637d3f24484e96dad9e992d3f62e

题目链接

【模板】01背包

题目描述

你有一个最大容量为 $W$ 的背包和 $N$ 件物品。第 $i$ 件物品的体积为 $w_i$ ，价值为 $v_i$ 。每件物品只有一件，可以选择放或不放。

题目要求计算两种方案下的最大总价值：

方案A：不要求装满背包。
方案B：要求最终恰好装满背包。如果无法恰好装满，则答案记为 $0$ 。

解题思路

这是经典的 01背包 问题，可以使用动态规划来解决。由于空间复杂度有要求，我们需要使用一维数组（滚动数组）进行优化。

我们定义 $dp[j]$ 为在背包容量为 $j$ 的限制下，所能获得的最大价值。我们的目标是求解两种不同要求下的 $dp[W]$ 。

核心状态转移方程：对于第 $i$ 件物品（体积 $w_i$ ，价值 $v_i$ ），要更新容量为 $j$ 的状态 $dp[j]$ ，我们有两种选择：

不放第 $i$ 件物品：最大价值保持不变，仍为 $dp[j]$ 。
放第 $i$ 件物品：前提是背包容量足够（ $j \ge w_i$ ）。放入后，价值为“未放入此物品时，容量为 $j-w_i$ 的最大价值” 加上此物品的价值，即 $dp[j-w_i] + v_i$ 。

因此，状态转移方程为： $dp[j] = \max(dp[j], dp[j-w_i] + v_i)$ 。为了保证每件物品只被选择一次，我们在更新 $dp$ 数组时，内层循环（遍历容量 $j$ ）需要从大到小（即从 $W$ 到 $w_i$ ）进行。

两种方案的区别在于初始化：

1. 方案A：不要求装满背包

初始化：我们将整个 $dp$ 数组初始化为 $0$ 。 $dp[0]=0$ 表示容量为 $0$ 时价值为 $0$ ，而其他 $dp[j]=0$ 则允许状态从“没有任何物品”开始转移。
求解：最终 $dp[W]$ 就是答案。由于状态转移中 $dp[j]$ 会继承 $dp[j-1]$ 的值，所以 $dp[W]$ 代表的是容量不超过 $W$ 时的最大价值。

2. 方案B：要求恰好装满背包

初始化：我们需要区分“状态可达”和“状态不可达”。
- $dp[0]$ 初始化为 $0$ ，表示“容量为0被恰好装满”，价值是 $0$ 。
- $dp$ 数组的其他所有位置（ $dp[1]$ 到 $dp[W]$ ）初始化为一个极小值（如负无穷），表示这些容量在初始时是“未被恰好装满”的不可达状态。
求解：一个状态只有从另一个可达状态转移而来时，它才变得可达。最终的 $dp[W]$ 如果仍然是负无穷，说明容量为 $W$ 的背包装不满，按题意输出 $0$ ；否则，输出 $dp[W]$ 。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long INF = -1e18; // 使用一个足够小的负数表示不可达

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    long long w;
    cin >> n >> w;

    vector<long long> w_items(n), v_items(n);
    for (int i = 0; i < n; ++i) {
        cin >> w_items[i] >> v_items[i];
    }

    // 方案A: 不要求装满
    vector<long long> dp_a(w + 1, 0);
    // 方案B: 要求恰好装满
    vector<long long> dp_b(w + 1, INF);
    dp_b[0] = 0;

    for (int i = 0; i < n; ++i) {
        for (long long j = w; j >= w_items[i]; --j) {
            dp_a[j] = max(dp_a[j], dp_a[j - w_items[i]] + v_items[i]);
            if (dp_b[j - w_items[i]] != INF) { // 只能从可达状态转移
                dp_b[j] = max(dp_b[j], dp_b[j - w_items[i]] + v_items[i]);
            }
        }
    }

    cout << dp_a[w] << "\n";
    if (dp_b[w] == INF) {
        cout << 0 << "\n";
    } else {
        cout << dp_b[w] << "\n";
    }

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int w = sc.nextInt();

        int[] wItems = new int[n];
        int[] vItems = new int[n];
        for (int i = 0; i < n; i++) {
            wItems[i] = sc.nextInt();
            vItems[i] = sc.nextInt();
        }

        // 方案A: 不要求装满
        long[] dpA = new long[w + 1];
        // 方案B: 要求恰好装满
        long[] dpB = new long[w + 1];
        Arrays.fill(dpB, -1); // 用-1表示不可达
        dpB[0] = 0;

        for (int i = 0; i < n; i++) {
            for (int j = w; j >= wItems[i]; j--) {
                dpA[j] = Math.max(dpA[j], dpA[j - wItems[i]] + vItems[i]);
                if (dpB[j - wItems[i]] != -1) { // 只能从可达状态转移
                    dpB[j] = Math.max(dpB[j], dpB[j - wItems[i]] + vItems[i]);
                }
            }
        }

        System.out.println(dpA[w]);
        if (dpB[w] == -1) {
            System.out.println(0);
        } else {
            System.out.println(dpB[w]);
        }
    }
}

n, w = map(int, input().split())
items = []
for _ in range(n):
    items.append(list(map(int, input().split())))

# 方案A: 不要求装满
dp_a = [0] * (w + 1)
# 方案B: 要求恰好装满
# 使用负无穷大表示不可达
dp_b = [-float('inf')] * (w + 1)
dp_b[0] = 0

for w_i, v_i in items:
    for j in range(w, w_i - 1, -1):
        dp_a[j] = max(dp_a[j], dp_a[j - w_i] + v_i)
        # 只能从可达状态转移
        if dp_b[j - w_i] != -float('inf'):
            dp_b[j] = max(dp_b[j], dp_b[j - w_i] + v_i)

print(dp_a[w])
if dp_b[w] == -float('inf'):
    print(0)
else:
    print(dp_b[w])