0/1 背包问题

问题描述

有 N 件物品，每件物品有重量 w_i 和价值 v_i，求在不超过背包容量 W 的情况下，选择物品使得总价值最大。

---

一维 DP

定义：dp[j] 为背包容量为 j 时的最大价值

初始条件：dp[j] = 0

状态转移： dp[j] = max (dp[j], dp[j − w] + v)

代码：

N, W = map(int, input().split())
dp = [0] * (W + 1)

for _ in range(N):
    w, v = map(int, input().split())
    for j in range(W, w - 1, -1):
        dp[j] = max(dp[j], dp[j - w] + v)

print(dp[W])

空间复杂度：O(W)

注意：一维 DP 中，内层循环需要倒序遍历，以确保每个物品只被使用一次。

---

为什么要倒序？

原因：避免同一物品被重复使用

以物品 (w=3, v=5) 为例：

正序遍历（错误）

for j in range(w, W + 1):  # 正序
    dp[j] = max(dp[j], dp[j-w] + v)

假设 W=6，初始 dp=[0,0,0,0,0,0,0]

j=3: dp[3] = max(0, dp[0]+5) = 5    # 放了这个物品
j=4: dp[4] = max(0, dp[1]+5) = 5    # dp[1] 是 0
j=5: dp[5] = max(0, dp[2]+5) = 5    # dp[2] 是 0
j=6: dp[6] = max(0, dp[3]+5) = max(0, 5+5) = 10   # 出问题了！

问题：dp[3] 刚刚被更新成 5，现在 dp[6] 又去查 dp[3]，相当于同一个物品用了两次！

倒序遍历（正确）

for j in range(W, w - 1, -1):  # 倒序
    dp[j] = max(dp[j], dp[j-w] + v)

j=6: dp[6] = max(0, dp[3]+5) = 5    # dp[3] 还是 0（未被当前物品更新）
j=5: dp[5] = max(0, dp[2]+5) = 5    # dp[2] 还是 0
j=4: dp[4] = max(0, dp[1]+5) = 5    # dp[1] 还是 0
j=3: dp[3] = max(0, dp[0]+5) = 5    # dp[0] 是 0

原因：倒序时，大 j 先更新，小 j 后更新。大 j 用到的 dp[j-w] 还是旧值，没被当前物品污染，确保每个物品只选一次。

---

二维 DP

定义：dp[i][j] 为考虑前 i 件物品，背包容量为 j 时的最大价值

初始条件：dp[0][j] = 0（没有物品时价值为 0）

状态转移： - 不选第 i 件物品：dp[i][j] = dp[i-1][j] - 选第 i 件物品：dp[i][j] = dp[i-1][j-w_i] + v_i

dp[i][j] = max (dp[i − 1][j], dp[i − 1][j − w_i] + v_i)

代码：

N, W = map(int, input().split())
dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    w, v = map(int, input().split())
    for j in range(W + 1):
        dp[i][j] = dp[i-1][j]
        if j >= w:
            dp[i][j] = max(dp[i][j], dp[i-1][j-w] + v)

print(dp[N][W])

时间复杂度：O(N × W) 空间复杂度：O(N × W)

---