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)

---

例题

例题 1：Book Shop（0-1 背包模板题）

来源：CSES - Book Shop

给定 n 本书，每本书有价格 $h_i$ 和页数 $s_i$，总预算为 x，求在预算范围内能获得的最大页数。每本书只能购买一次。

限制：$1 \le n \le 1000$，$1 \le x \le 10^5$，$1 \le h_i, s_i \le 1000$。

示例：输入 4 10，h = [4, 8, 5, 3]，s = [5, 12, 8, 1]；输出 13（购买第 1 和第 3 本书，价格 4+5=9，页数 5+8=13）。

思路：0-1 背包（每本书只能选一次）。dp[j] 为花费不超过 j 时能获得的最大页数，初始 dp[j] = 0，转移：

$$dp[j] = \max(dp[j],\ dp[j - h_i] + s_i)$$

对每本书尝试加入背包，倒序遍历 j 确保每本书只被使用一次。

n, x = map(int, input().split())
cost = [int(x) for x in input().split()]
pages = [int(x) for x in input().split()]

dp = [0] * (x + 1)

for i in range(n):
    for j in range(x, cost[i] - 1, -1):
        dp[j] = max(dp[j], dp[j - cost[i]] + pages[i])

print(dp[x])

复杂度：时间 O(n × x)，空间 O(x)。

注意：0-1 背包需要倒序遍历，确保每本书只选一次；完全背包则正序遍历。

例题 2：Money Sums（可行性背包）

来源：CSES - Money Sums

给定 n 枚硬币，每枚硬币价值 $x_i$，求能凑成的所有不同金额。

限制：$1 \le n \le 100$，$1 \le x_i \le 1000$。

示例：输入 4，coins = [4, 2, 5, 2]；输出 9 种金额：2 4 5 6 7 8 9 11 13。

思路：0-1 背包求可行性（每枚硬币只能用一次）。dp[j] 表示能否凑成金额 j，初始 dp[0] = True（什么都不选），转移：

$$dp[j] = dp[j]\ \text{或}\ dp[j - x_i] \quad (j - x_i \geq 0)$$

n = int(input())
coins = list(map(int, input().split()))

max_sum = sum(coins)
dp = [False] * (max_sum + 1)
dp[0] = True

for coin in coins:
    for j in range(max_sum, coin - 1, -1):
        if dp[j - coin]:
            dp[j] = True

res = [i for i in range(1, max_sum + 1) if dp[i]]

print(len(res))
print(*res)

复杂度：时间 O(n × max_sum)，空间 O(max_sum)。

例题 3：Two Sets II（计数背包）

来源：CSES - Two Sets II

给定数字 1, 2, …, n，求将其分成两个和相等集合的方式数（对 $10^9+7$ 取模）。

限制：$1 \le n \le 500$。

示例：输入 7，输出 4：

• {1,3,4,6} 和 {2,5,7}
• {1,2,5,6} 和 {3,4,7}
• {1,2,4,7} 和 {3,5,6}
• {1,6,7} 和 {2,3,4,5}

思路：0-1 背包求方案数（每个数字只能用一次）。

分析：数字 1~n 的总和为 $S = n(n+1)/2$；S 为奇数无法平分输出 0；否则目标是在一半和 $S/2$ 内放入一些数字。dp[j] 为凑成和 j 的方式数，初始 dp[0] = 1（什么都不选），转移：

$$dp[j] = dp[j] + dp[j - i] \quad \text{for all } i \text{（倒序）}$$

import sys

MOD = 10**9 + 7

n = int(input())

sum_elem = n * (n + 1) // 2

if sum_elem % 2 == 1:
    print(0)
    sys.exit()

target = sum_elem // 2

dp = [0] * (target + 1)
dp[0] = 1

for i in range(1, n):
    for j in range(target, i - 1, -1):
        dp[j] = (dp[j] + dp[j - i]) % MOD

print(dp[target])

复杂度：时间 O(n × target)，空间 O(target)。

为什么只用 1~n-1？ 假设 n 在较小的那组，那么较小那组的最大可能和为 $1+2+\dots+(n-1) = n(n-1)/2$；由于 $S/2 = n(n+1)/4 > n(n-1)/4$，n 不可能在较小的那组。因此 n 一定在较大的那组，只需用 1~n-1 来凑成 $S/2$。

验证：n = 7，总和 = 28，目标 = 14。用数字 1~6 凑成 14 的 4 种方式，加上数字 7，正好对应 4 种分组方式。

---