背包：选与不选
本节目标：能手写 0/1 背包与完全背包，并说清内层循环的方向为什么一个逆序、一个正序。
从选与不选说起
背包问题的骨架只有一句话：每一件物品，要么拿，要么不拿。 拿了就占掉它的重量、换来它的价值；不拿就什么都不占。
给定几件物品，每件有重量和价值，再给一个容量上限，问能装下的最大总价值是多少。
先写一个绝对正确的版本：把所有子集都枚举一遍。它慢，但它是后面一切写法的裁判。
def brute01(w, v, C):
"""枚举所有子集——0/1 背包的标准答案，物品少的时候才能用。"""
best = 0
n = len(w)
for mask in range(1 << n):
tw = tv = 0
for i in range(n):
if mask >> i & 1:
tw += w[i]
tv += v[i]
if tw <= C and tv > best:
best = tv
return best
def knap01_2d(w, v, C):
"""0/1 背包 · 二维：dp[i][c] = 只看前 i 件、容量 c 的最大价值。"""
n = len(w)
dp = [[0] * (C + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for c in range(C + 1):
dp[i][c] = dp[i - 1][c] # 不拿第 i 件
if c >= w[i - 1]:
dp[i][c] = max(dp[i][c], dp[i - 1][c - w[i - 1]] + v[i - 1]) # 拿
return dp[n][C]
def knap01_1d_rev(w, v, C):
"""0/1 背包 · 一维滚动数组 · 内层逆序（对）。"""
dp = [0] * (C + 1)
for i in range(len(w)):
for c in range(C, w[i] - 1, -1):
dp[c] = max(dp[c], dp[c - w[i]] + v[i])
return dp[C]
W = [2, 3, 4, 5]
V = [3, 4, 5, 6]
C = 8
print(f' 物品 (重量, 价值): {list(zip(W, V))} 容量 {C}')
print(f' 二维 : {knap01_2d(W, V, C)}')
print(f' 一维 · 内层逆序（对） : {knap01_1d_rev(W, V, C)}')
print(f' 枚举所有子集 : {brute01(W, V, C)}') 物品 (重量, 价值): [(2, 3), (3, 4), (4, 5), (5, 6)] 容量 8
二维 : 10
一维 · 内层逆序（对） : 10
枚举所有子集 : 10三种写法答案一致：10（拿重量 3 和重量 5 那两件，价值 4 + 6）。容量刚好用满。
二维写法
dp[i][c] 读作「只看前 i 件物品、容量上限是 c 时，能拿到的最大价值」。这个定义里有两个「只看」，都要说清：
- 只看前 i 件——第 i+1 件之后的一概不考虑；
- 容量上限是 c——不是「正好用掉 c」。
转移就是这几行：
def knap01_fill(dp, i, c, w, v):
"""填 dp 的第 i 行第 c 格。"""
dp[i][c] = dp[i - 1][c] # 不拿第 i 件：答案跟前 i-1 件一样
if c >= w[i - 1]:
dp[i][c] = max(dp[i][c],
dp[i - 1][c - w[i - 1]] + v[i - 1]) # 拿：腾出容量，价值加 v[i-1]
return dp[i][c]第二行是背包的灵魂：拿第 i 件之后，剩下要解决的问题正好是「只看前 i-1 件、容量 c - w_{i-1}」——规模变小了，而且形状不变。这就是上一课说的最优子结构。
注意拿的那一支查的是 dp[i-1]，不是 dp[i]。这个下标就是下一节一切差别的源头。
压成一维：滚动数组
二维表有 (n+1) \times (C+1) 格，但算第 i 行时只用到第 i-1 行。于是可以只用一行，反复覆盖它自己。
dp = [0] * (C + 1)
for i in range(len(W)):
for c in range(C, W[i] - 1, -1): # 从大到小
dp[c] = max(dp[c], dp[c - W[i]] + V[i])dp[c] 在赋值前是「前 i-1 件的结果」，赋值后是「前 i 件的结果」——同一格身兼两职。
代价是必须从大到小遍历容量。为什么？看下一节。
内层循环的方向
把上面那个循环的方向改成正序，其他一个字都不动：
def knap01_1d_fwd(w, v, C):
"""0/1 背包 · 一维 · 内层正序（错：同一件物品会被重复选）。"""
dp = [0] * (C + 1)
for i in range(len(w)):
for c in range(w[i], C + 1):
dp[c] = max(dp[c], dp[c - w[i]] + v[i])
return dp[C]
def knap_complete(w, v, C):
"""完全背包 · 一维 · 内层正序（对：每件物品可以拿任意多件）。"""
dp = [0] * (C + 1)
for i in range(len(w)):
for c in range(w[i], C + 1):
dp[c] = max(dp[c], dp[c - w[i]] + v[i])
return dp[C]
for C2 in (6, 8, 10, 12):
print(f' 容量 {C2:>2}: 逆序 {knap01_1d_rev(W, V, C2):>3}'
f' 正序 {knap01_1d_fwd(W, V, C2):>3}'
f' 枚举 {brute01(W, V, C2):>3}'
f' 正序 == 完全背包? {knap01_1d_fwd(W, V, C2) == knap_complete(W, V, C2)}') 容量 6: 逆序 8 正序 9 枚举 8 正序 == 完全背包? True
容量 8: 逆序 10 正序 12 枚举 10 正序 == 完全背包? True
容量 10: 逆序 13 正序 15 枚举 13 正序 == 完全背包? True
容量 12: 逆序 15 正序 18 枚举 15 正序 == 完全背包? True正序版本的答案和完全背包一模一样，而且都比枚举出来的正确答案大。 它错得很有规律。
原因在「一格身兼两职」这件事上。正序遍历时，算 dp[c] 用到的 dp[c - w[i]] 在本轮已经被更新过了——也就是说那一格已经是「前 i 件」的结果，可能已经拿过第 i 件。于是同一件物品被拿了第二次、第三次。
容量 6、物品 1 是（重量 2，价值 3）：正序等于把它拿了三次（2+2+2），价值 9。可 0/1 背包里它只有一件。
逆序就没有这个问题：算 dp[c] 时 dp[c - w[i]] 的下标更小，逆序还没走到那儿，所以它一定还是「前 i-1 件」的结果——没有拿过第 i 件。
一句话记住：同一件物品能不能被重复选，决定了内层循环的方向。
| 0/1 背包（每件只有一件） | 完全背包（每件可以拿任意多） | |
|---|---|---|
| 内层容量循环 | 逆序（从 C 到 w[i]） | 正序（从 w[i] 到 C） |
| 正向读到的 dp[c-w[i]] | 上一件物品时的结果 | 本轮已更新过的结果 |
| 含义 | 这件物品还没被拿过 | 这件物品已经可以再拿一次 |
完全背包：正序就是答案
完全背包允许每件物品拿任意多件，所以正序就是对的。上一节已经看到：同一段代码在 0/1 背包里是错的，在这里是对的。
拿它跟「按容量从小到大逐个推」的写法对拍：
def brute_complete(w, v, C):
"""完全背包的参照实现：按容量从小到大推。"""
dp = [0] * (C + 1)
for c in range(1, C + 1):
for i in range(len(w)):
if w[i] <= c:
dp[c] = max(dp[c], dp[c - w[i]] + v[i])
return dp[c]
import random
random.seed(11)
bad_c = 0
for _ in range(300):
n = random.randint(1, 5)
ws = [random.randint(1, 8) for _ in range(n)]
vs = [random.randint(1, 15) for _ in range(n)]
cc = random.randint(1, 25)
if knap_complete(ws, vs, cc) != brute_complete(ws, vs, cc):
bad_c += 1
print(f' 300 组随机数据上，完全背包（正序）与逐容量递推不一致的有 {bad_c} 组')
W3 = [2, 3, 4]
V3 = [3, 4, 5]
print(f' 小例子 重量 {W3} 价值 {V3}：')
for C4 in (4, 6, 8, 10, 12):
print(f' 容量 {C4:>2}: 0/1 背包 {knap01_1d_rev(W3, V3, C4):>3}'
f' 完全背包 {knap_complete(W3, V3, C4):>3}'
f' 枚举(0/1) {brute01(W3, V3, C4):>3}') 300 组随机数据上，完全背包（正序）与逐容量递推不一致的有 0 组
小例子 重量 [2, 3, 4] 价值 [3, 4, 5]：
容量 4: 0/1 背包 5 完全背包 6 枚举(0/1) 5
容量 6: 0/1 背包 8 完全背包 9 枚举(0/1) 8
容量 8: 0/1 背包 9 完全背包 12 枚举(0/1) 9
容量 10: 0/1 背包 12 完全背包 15 枚举(0/1) 12
容量 12: 0/1 背包 12 完全背包 18 枚举(0/1) 12完全背包的答案永远不小于 0/1 背包——可选的方案多了（允许重复拿），最大值只会更大或不变。容量 8 时它给 12，是把（重量 4，价值 5）拿了两次；0/1 背包里那件只有一件，只能给 9。
恰好装满与不超过
前面所有写法回答的都是「不超过容量 C 的最大价值」。还有一问：恰好装满容量 C 的最大价值是多少？（有时无解。）
两者代码只差初始化：
NEG = float('-inf')
def knap01_exact(w, v, C):
"""恰好装满：只把 dp[0] 设 0，其余全是负无穷。"""
dp = [NEG] * (C + 1)
dp[0] = 0
for i in range(len(w)):
for c in range(C, w[i] - 1, -1):
if dp[c - w[i]] != NEG:
dp[c] = max(dp[c], dp[c - w[i]] + v[i])
return dp[C]
def knap01_exact_badinit(w, v, C):
"""恰好装满，但初始化照「不超过」那版写成了全 0。"""
dp = [0] * (C + 1)
for i in range(len(w)):
for c in range(C, w[i] - 1, -1):
dp[c] = max(dp[c], dp[c - w[i]] + v[i])
return dp[C]
W2 = [3, 5, 7]
V2 = [3, 5, 7]
print(f' 物品 (重量, 价值): {list(zip(W2, V2))}（价值 = 重量，所以「装满多少」就是价值）')
print(' 容量 恰好装满 初始化写成全 0 这个容量能恰好凑出来吗')
for C3 in range(1, 16):
ex = knap01_exact(W2, V2, C3)
bd = knap01_exact_badinit(W2, V2, C3)
print(f' {C3:>4} {str(ex):>8} {bd:>15} {"能" if ex != NEG else "不能"}') 物品 (重量, 价值): [(3, 3), (5, 5), (7, 7)]（价值 = 重量，所以「装满多少」就是价值）
容量 恰好装满 初始化写成全 0 这个容量能恰好凑出来吗
1 -inf 0 不能
2 -inf 0 不能
3 3 3 能
4 -inf 3 不能
5 5 5 能
6 -inf 5 不能
7 7 7 能
8 8 8 能
9 -inf 8 不能
10 10 10 能
11 -inf 10 不能
12 12 12 能
13 -inf 12 不能
14 -inf 12 不能
15 15 15 能重量 3、5、7 能凑出的数只有 0、3、5、7、8、10、12、14、15……，容量 1、2、4、6、9、11、13 根本凑不出来，正确答案是「无解」。
初始化写成全 0 之后，它在这些容量上交回的是 不超过 的答案（比如容量 11 给 10）——一个看着很正常、也确实是某个问题的答案的数，只是回答的不是你问的那个问题。
为什么 -inf 能挡住？因为 dp[c - w] 是 -inf 时，-inf + v 还是 -inf，比 -inf 不大，那一格就不会被填上。没填上就等于「这个容量凑不出来」。
小数据对拍
背包的写法变体多，靠读代码看不出对错。对拍是最省事的办法：小数据上枚举所有子集，跟你的写法逐组比。
import random
random.seed(5)
bad_rev = bad_fwd = 0
trials = 400
for _ in range(trials):
n = random.randint(1, 8)
ws = [random.randint(1, 9) for _ in range(n)]
vs = [random.randint(1, 20) for _ in range(n)]
cc = random.randint(1, 20)
want = brute01(ws, vs, cc)
if knap01_1d_rev(ws, vs, cc) != want:
bad_rev += 1
if knap01_1d_fwd(ws, vs, cc) != want:
bad_fwd += 1
print(f' {trials} 组随机数据（n≤8、容量≤20）：')
print(f' 内层逆序与枚举不一致的有 {bad_rev} 组')
print(f' 内层正序与枚举不一致的有 {bad_fwd} 组')
rng = random.Random(5)
first = None
for _ in range(4000):
n = rng.randint(1, 8)
ws = [rng.randint(1, 9) for _ in range(n)]
vs = [rng.randint(1, 20) for _ in range(n)]
cc = rng.randint(1, 20)
if knap01_1d_fwd(ws, vs, cc) != brute01(ws, vs, cc):
first = (ws, vs, cc, brute01(ws, vs, cc), knap01_1d_fwd(ws, vs, cc))
break
if first:
ws, vs, cc, want, got = first
print(f' 揪出一组：重量 {ws}、价值 {vs}、容量 {cc}')
print(f' 逆序给 {knap01_1d_rev(ws, vs, cc)}、正序给 {got}、枚举给 {want}') 400 组随机数据（n≤8、容量≤20）：
内层逆序与枚举不一致的有 0 组
内层正序与枚举不一致的有 297 组
揪出一组：重量 [6, 9, 1, 8, 4]、价值 [2, 6, 4, 12, 16]、容量 8
逆序给 20、正序给 32、枚举给 20逆序 0 组错，正序 297 组错——400 组里错了四分之三。注意它错的方式：答案总是偏大。背包问题里「偏大」就是铁证，因为一个偏大的答案意味着某种你其实没有的资源被用掉了（这里是同一件物品被拿了多次）。
对拍的三个要点：
- 数据要小，小到能枚举（这里 n \le 8，2^8 = 256 个子集）。
- 数据要随机，也要有边界：重量为 1 的、价值为 0 的、容量刚好等于某件物品重量的，都该出现几次。
- 错的那一组要打印出来，人眼扫一遍往往就能看出是哪类情况。
变形：分组背包
背包的变形很多，骨架都是「选与不选」，只是多了一层约束。
分组背包：物品分成若干组，每组最多选一件。写法只多一层循环：
import itertools
groups = [[(2, 3), (3, 4)], [(4, 5), (5, 6)], [(1, 8)]]
def knap_group(groups, C):
"""外层遍历组、中层遍历容量（逆序）、内层遍历组内物品。"""
dp = [0] * (C + 1)
for g in groups:
for c in range(C, -1, -1):
for gw, gv in g:
if c >= gw:
dp[c] = max(dp[c], dp[c - gw] + gv)
return dp[C]
def brute_group(groups, C):
"""枚举：每组有三种可能——不选、选第 1 件、选第 2 件……"""
best = 0
for pick in itertools.product(*[range(-1, len(g)) for g in groups]):
tw = tv = 0
for i, j in enumerate(pick):
if j >= 0:
tw += groups[i][j][0]
tv += groups[i][j][1]
if tw <= C and tv > best:
best = tv
return best
for C5 in range(1, 13):
a, b = knap_group(groups, C5), brute_group(groups, C5)
print(f' 容量 {C5:>2}: 分组背包 {a:>3} 枚举 {b:>3} 一致 {a == b}') 容量 1: 分组背包 8 枚举 8 一致 True
容量 2: 分组背包 8 枚举 8 一致 True
容量 3: 分组背包 11 枚举 11 一致 True
容量 4: 分组背包 12 枚举 12 一致 True
容量 5: 分组背包 13 枚举 13 一致 True
容量 6: 分组背包 14 枚举 14 一致 True
容量 7: 分组背包 16 枚举 16 一致 True
容量 8: 分组背包 17 枚举 17 一致 True
容量 9: 分组背包 18 枚举 18 一致 True
容量 10: 分组背包 18 枚举 18 一致 True
容量 11: 分组背包 18 枚举 18 一致 True
容量 12: 分组背包 18 枚举 18 一致 True循环顺序的规矩：组在外层，容量在中层（逆序），组内物品在最里层。 容量逆序保证这一组不会被选两次——它跟 0/1 背包是同一个道理，只不过「一件物品」换成了「一组里的一个选择」。
这类变形看着多，其实只要问三句话就能归位：
- 每件能拿几次？ 一次 → 逆序；任意多次 → 正序。
- 有没有「每组最多一件」这类分组约束？ 有 → 加一层组循环。
- 问的是「不超过」还是「恰好」？ 恰好 → 非法状态设负无穷。
这一课用到的判断
- 背包的骨架是「选与不选」：
dp[i][c]读作「只看前 i 件、容量上限是 c 的最大价值」。拿第 i 件时查的是dp[i-1][c - w]——上一个下标是 i-1，这是方向问题的源头。 - 一维滚动数组让一格身兼两职：赋值前是「前 i-1 件」的结果，赋值后是「前 i 件」的。
- 方向由「同一件能不能重复选」决定：0/1 背包内层逆序（正向读到的
dp[c-w]还没被本轮更新，所以那件还没拿过）；完全背包内层正序（读到的是已更新值，可以再拿一次）。 - 0/1 写成正序的后果是答案偏大，而且恰好等于完全背包：实测四个容量上「正序 == 完全背包」全部为真。400 组对拍里正序错 297 组、逆序错 0 组。容量 6 时正序等于把（重量 2，价值 3）拿了三次，可它只有一件。
- 背包答案「偏大」就是铁证：偏大意味着用掉了你其实没有的资源。
- 「恰好装满」靠初始化区分：只把
dp[0]设 0，其余全设-inf。-inf + v仍是-inf，那一格永远填不上，等于「这个容量凑不出来」。 - 初始化写错会回答另一个问题：全 0 初始化让「恰好装满」悄悄交回「不超过」的答案。重量 3、5、7 时，容量 11 的正确回答是「无解」，写错初始化给 10——正常、合法、但答非所问。
- 变形只要问三句话：每件拿几次（定方向）、有没有分组约束（加循环）、问不超过还是恰好（定初始化）。分组背包的循环顺序是「组在外、容量在中逆序、组内物品在最里」。
上手做
四个任务加一次对拍
这一课配了动手练习，在 lab/0025-dp-knapsack/。
task1_knap01.py：把 0/1 背包的二维版与一维逆序版写出来，两版答案必须一致。task2_direction.py：把内层写成正序，跟枚举出的正确答案对拍，看它错在哪、错的方式是不是「总是偏大」。task3_exact.py：实现「恰好装满」，并把非法状态设成负无穷；再故意改成全 0 初始化，对比两种答案。task4_complete_group.py：写完全背包与分组背包，各自在随机小数据上跟暴力版对拍。
跑法、判分在读什么、卡住了先看哪里，都写在该目录的说明与 ../lab/README.md 里。写完想对照，看 lab/solutions/。
没看懂？随时问
把看不懂的段落（或报错）原样复制回会话，说一句哪里不懂就行，我只解释这一段，不打断你的进度。