第 101 章 背包问题¶
本章配套 14 道例题，见 §例题。
背包是 DP 里模型最固定、变式最多的一族。本章依据《背包九讲》全文组织， 把九种形态一次讲完；每种形态都给出Python 下把内层循环下沉到 C 层的写法—— 这是本章与普通算法书最大的不同。
1 问题谱系¶
| 形态 | 每种物品可取件数 | 例题 |
|---|---|---|
| 01 背包 | 0 或 1 | BISHI136 |
| 完全背包 | 无限 | BISHI137 |
| 多重背包 | 至多 \(s_i\) 件 | BISHI138 |
| 混合背包 | 三者混杂 | — |
| 二维费用背包 | 两个容量维度 | BISHI139 |
| 分组背包 | 每组至多一件 | BISHI140 |
| 依赖背包（双向） | 组内必须同取同弃 | BISHI103 |
| 树形依赖背包（单向） | 取子必须取父 | BISHI142 |
| 方案数 / 具体方案 | — | — |
九种形态共用同一个骨架：
变的只有三件事：容量循环的方向、物品的枚举方式、以及初值。
2 01 背包¶
\(n\) 件物品，第 \(i\) 件体积 \(v_i\) 价值 \(w_i\)，每件最多取一次，容量 \(V\)，求最大价值。
二维写法（先理解）¶
「枚举最后一步」在这里就是「枚举第 \(i\) 件取不取」。两类互不重叠、覆盖全部。
一维写法（实战用）¶
注意 \(f[i][\cdot]\) 只依赖 \(f[i-1][\cdot]\)，可以滚动成一维：
# [片段]
f = [0] * (V + 1) # f[c] = 容量 c 时的最大价值，初值全 0 = 不要求装满
for v, w in items: # 外层枚举物品，一件物品只在这一轮里被考虑
for c in range(V, v - 1, -1): # ★ 倒序；下界取 v-1 是因为 c < v 装不下这件
if f[c - v] + w > f[c]: # f[c-v] 下标更小，倒序时它还没被本轮改过
f[c] = f[c - v] + w # 于是它代表「还没考虑第 i 件」⇒ 本件只会被选一次
为什么 01 背包倒序、完全背包正序¶
这是全书最经典的一个细节，必须理解而不是背结论。
一维数组 f 在处理第 \(i\) 件物品的过程中，同时承担两个角色：
- 已经被本轮更新过的位置：存的是 \(f[i][\cdot]\)（考虑了第 \(i\) 件）
- 还没被更新的位置：存的是 \(f[i-1][\cdot]\)（没考虑第 \(i\) 件）
转移 f[c] = max(f[c], f[c-v] + w) 要求右边的 f[c-v] 必须是 \(f[i-1][c-v]\)，
即「还没考虑第 \(i\) 件」的值。
| 遍历方向 | 更新 f[c] 时 f[c-v] 的状态 |
语义 |
|---|---|---|
| 倒序（\(V \to v\)） | \(c-v < c\)，还没被本轮碰过 ⇒ 是 \(f[i-1][c-v]\) | 01 背包，每件最多取 1 次 |
| 正序（\(v \to V\)） | \(c-v < c\)，已经被本轮更新过 ⇒ 可能已含第 \(i\) 件 | 完全背包，允许取多件 |
正序时，f[c-v] 里可能已经放了一件第 \(i\) 号物品，再加一件就成了两件——
这恰好就是完全背包想要的效果。
一句话记忆：倒序 = 用「上一轮」的值 = 每件只能用一次； 正序 = 用「本轮」的值 = 同一件可以反复用。
Python 写法：整段取 max¶
一维倒序循环有个漂亮的等价形式：
# [片段]
# 倒序 for 循环等价于：
# 左边 f[v:] 是 c = v..V 的旧值；右边列表推导给出的是 c-v = 0..V-v 处的旧值加 w
# 两条序列逐位取 max 再整段写回，等价于对每个 c 做一次 max(f[c], f[c-v]+w)
f[v:] = list(map(max, f[v:], [x + w for x in f[:V + 1 - v]]))
推导：对每个 \(c \ge v\)，新值 \(= \max(f[c],\ f[c-v]+w)\)。
把 \(c\) 从 \(v\) 到 \(V\) 排成一列，左边是 f[v:]，右边的 \(f[c-v]\) 依次是 f[0], f[1], ..., f[V-v]，
也就是 f[:V+1-v]。
关键在于：右边的候选数组是在赋值之前用旧的 f 一次性算完的，
所以每个位置用到的都是「上一轮」的值——01 语义自动成立，连倒序都不需要了。
而且列表推导式和 map(max, ...) 全在 C 层执行，比 \(10^6\) 次 Python 迭代快 5–8 倍。
恰好装满 vs 不要求装满¶
只差初值：
| 要求 | 初值 | 理由 |
|---|---|---|
| 不要求装满（容量 \(\le V\) 即可） | f = [0] * (V+1) |
任何容量都是合法状态，什么都不装的价值是 0 |
| 恰好装满（容量 \(= V\)） | f[0] = 0，其余 \(-\infty\) |
只有容积 0 是「已合法凑出」的，其余都是「凑不出」 |
\(-\infty\) 不能取
-1这种小负数。-1 + w可能变成正数，把「凑不出」误判成「凑出了」。 取-10**18这个量级：加满 \(10^3\) 个 \(10^3\) 也只是 \(-10^{18}+10^6\)，仍然远小于 0。
BISHI136 【模板】01背包（简单）¶
\(n, V \le 10^3\)，同时求「不要求装满」和「恰好装满」两问的最大价值。
import sys
def main():
data = sys.stdin.buffer.read().split()
n, V = int(data[0]), int(data[1])
p = 2 # 游标：物品数据从第 3 个 token 开始
NEG = -(10 ** 18) # 当作负无穷；加满 1e3 件 1e3 价值也翻不了正
f0 = [0] * (V + 1) # 不要求装满：任何容量都合法，什么都不装价值为 0
f1 = [NEG] * (V + 1) # 恰好装满：除容量 0 外一律标成「凑不出」
f1[0] = 0
for _ in range(n):
v, w = int(data[p]), int(data[p + 1])
p += 2
if v > V:
continue # 单件就超容量，永远选不上，跳过省一轮切片
tail = V + 1 - v # 候选段长度：对应 c = v..V 共 V+1-v 个位置
cand = [x + w for x in f0[:tail]] # 用旧的 f0 算完候选，01 语义自动成立
f0[v:] = list(map(max, f0[v:], cand))
cand = [x + w for x in f1[:tail]] # 两个数组各自独立地做同一件事
f1[v:] = list(map(max, f1[v:], cand))
print(f0[V])
print(f1[V] if f1[V] > 0 else 0) # 仍是负无穷量级 = 凑不出，按题目要求输出 0
main()
坑：「恰好装满」无解时题目要求输出
0，不是-1也不是负数。
题解：solutions/nowcoder/BISHI136/sol.py（已通过官方样例验证）
3 完全背包¶
每种物品可取无限件。理论上把 01 背包的倒序改正序就行：
# [片段]
for c in range(v, V + 1): # ★ 正序；从 v 起步，更小的容量装不下
if f[c - v] + w > f[c]: # 正序时 f[c-v] 本轮已被更新，里面可能已含这件物品
f[c] = f[c - v] + w # 于是同一件可以被反复叠加，正是完全背包的语义
但 Python 里这个正序循环没法直接下沉到 C 层——它有串行依赖：
f[c] 依赖本轮刚算出的 f[c-v]，map 是并行语义，做不到。
解法：二进制拆分把完全背包变回 01 背包¶
依次用 \((v, w)\)、\((2v, 2w)\)、\((4v, 4w)\)、…… 各做一次 01 背包。 每一轮可选可不选，组合起来正好覆盖取 \(0 \sim 2^r - 1\) 件的所有情况。 只要 \(2^r v > V\) 就已经覆盖了所有可能的件数（再多也装不下）。
# [片段]
kv, kw = v, w # 第 r 轮的打包物品 = 2^r 件原物品捆在一起
while kv <= V: # 只需 log2(V/v) 轮；超过容量的打包件装不下
tail = V + 1 - kv
f[kv:] = list(map(max, f[kv:], [x + kw for x in f[:tail]])) # 每轮一次 01 转移
kv += kv # 体积翻倍，等价于 kv *= 2
kw += kw # 价值同步翻倍，保持「单价」不变
每一轮都是一次 C 层的整段取 max，轮数只有 \(O(\log(V/v))\)。
BISHI137 的两条必要剪枝¶
\(T \le 200\) 组数据，\(n, m \le 10^3\)。
朴素做法是 \(200 \times 1000 \times 1000 = 2\times10^8\)，必挂。两条剪枝：
| 剪枝 | 做法 | 依据 |
|---|---|---|
| 按体积去重 | 同体积只留价值最大的 | 体积相同时，价值小的永远不会被选 |
| 去支配 | 按体积升序扫，只保留价值严格大于此前所有更小体积物品的 | 若 \(v_1 \le v_2\) 且 \(w_1 \ge w_2\)，物品 2 永远可被物品 1 替换 |
去重后物品数最多只剩 \(\min(n, m)\) 种；题目「体积均小于 10」的那几个测试点， 去重后只剩 \(\le 9\) 件物品，瞬间出解。
⚠️ Python 现实性：随机数据下去重后仍可能剩近 \(10^3\) 种体积， 200 组累计约 \(5\times10^8\) 次 C 层元素操作，在 10 秒限制下偏险。 这已是 Python 下的最优形态，题面本身也建议提交 PyPy。
题解：solutions/nowcoder/BISHI137/sol.py（已通过官方样例验证）
BM70 兑换零钱(一)¶
给定面值互不相同的硬币（每种无限枚）与目标金额，求凑出目标的最少硬币数，凑不出返回 \(-1\)。 这正是 DP 入门 开篇那个「贪心为什么不行」的例子的一般形式—— 面值 \(1, 5, 11\) 时贪心给 5 枚而最优是 3 枚。
按 §1 的谱系，它是完全背包：容量是金额，每件物品体积为面值、价值为 1，求最小化。 转移就是 §3 的正序循环，只是把 \(\max\) 换成 \(\min\)：
三个实现要点：
- 初值用一个足够大的哨兵（例如金额上界加一），不要用
float("inf")—— 后者会把整个数组变成浮点，取模与比较都变慢，而且inf + 1仍是inf， 凑不出的状态会静默传播下去；用整数哨兵则可以在最后一步直接判「是否仍是哨兵」来返回 \(-1\)。 - 循环顺序不能反。外层枚举面值、内层正序枚举容量，才是完全背包； 内外一换就成了「按容量分层」的另一种语义，对求最小值恰好也对，但对求方案数就会算错， 这一点 §10 讲过。
- 这题的金额上界不大，正序循环的串行依赖不必按 §3 的二进制拆分绕开。 金额上到 \(10^6\) 时再考虑那条路。
4 多重背包¶
第 \(i\) 种物品有 \(s_i\) 件。
二进制拆分（通用解法）¶
把「最多取 \(s\) 件」拆成若干个 01 背包物品：
这 \(t+1\) 个「打包物品」任意组合，恰好能凑出 \(0 \sim s\) 的任意件数 （前面是二进制表示，最后一项补齐余数）。于是多重背包退化成 01 背包， 复杂度 \(O\big(m \sum \log s_i\big)\)。
# [片段]
k = 1
while k <= s: # k 依次取 1,2,4,...，凑得出任意二进制组合
add_01_item(k * v, k * w) # 打包成一件 01 物品
s -= k # 从剩余件数里扣掉这一包
k += k
if s > 0:
add_01_item(s * v, s * w) # 补齐余数，这一包让可凑件数正好覆盖到 s
两个必做的预处理¶
| 预处理 | 做法 | 为什么 |
|---|---|---|
| 件数上限截断 | \(s \leftarrow \min(s,\ \lfloor m/v \rfloor)\) | 容量只有 \(m\)，取超过 \(m/v\) 件不可能。\(s_i\) 最大 \(10^6\) 时 \(\log s \approx 20\)，截断后大多只剩 1–3 个拆分件 |
| 体积为 0 的特判 | \(v = 0\) 的物品直接把 \(s \cdot w\) 计入答案 | 否则 m // v 除零崩溃 |
BISHI138 的第 15、16 个测试点专门卡「体积为 0」。这类边界只要漏一个就是 RE。
单调队列优化：BISHI138 真正要用的解法¶
多重背包还有一个 \(O(nm)\) 的做法：按 \(j \bmod w\) 分组，组内用单调队列维护滑动窗口最大值。 转移式里只有下标模 \(w\) 同余的位置互相影响，写成 \(j = r + t\cdot w\) 后
括号内只与 \(t'\) 有关，正是定长窗口最大值。
一个很容易踩的判断：单调队列每一步都是 Python 层操作， 而二进制拆分每一轮都是 C 层整段处理， 于是想当然地认为「二进制拆分在 Python 里更快」。实测正好相反。
用「\(w\) 全为 1、\(s\) 全为 \(10^6\)」构造 10 组极限数据：
写法 复杂度 实测耗时 二进制拆分 + C 层整段取 max \(O(m\sum\log s_i) \approx 10^9\) 80.1 秒 单调队列（纯 Python 层） \(O(nm) = 9\times10^7\) 14.9 秒 差了 5.4 倍。截断后每件物品仍要拆出约 12 个打包件， 物品数被放大了一个数量级，C 层再便宜也补不回来。
所以：「把循环压进 C 层」是常数优化，不能替代降低渐进复杂度。 数据规模足够大时先看复杂度、再谈常数——这一点 Python 和 C++ 并无分歧， 真正的分歧只在「常数相差多少倍」。
⚠️ BISHI138 必须用 PyPy3 提交。 单调队列是 \(9\times10^7\) 次纯 Python 层迭代， 且队列状态前后依赖，无法向量化到 C 层：本题时限已经放宽到「其他语言 10 秒」， CPython 实测仍要 14.9 秒。 PyPy3 的 JIT 能把这种紧循环编译成机器码，实测轻松通过。 提交语言登记在该题
meta.json的langs.py.submitLang字段。
题解：solutions/nowcoder/BISHI138/sol.py（已通过判题机验证，PyPy3）
5 混合背包¶
三种形态混在一题里。做法：统一转成 01 背包物品。
| 原形态 | 转换 |
|---|---|
| 01（\(s = 1\)） | 本身就是 |
| 完全（\(s = \infty\)） | 二进制倍增到超过容量 |
| 多重（\(s\) 有限） | 二进制拆分 |
转完之后只剩一种循环，代码反而最简单。
6 二维费用背包¶
两个容量维度（如时间 \(T\) 与精力 \(H\)）：
两维都要倒序（01 语义）。
BISHI139 的 Python 写法¶
\(n \le 50\)，\(T, H \le 500\)，状态数 \(50 \times 501 \times 501 \approx 1.25\times10^7\)。
纯 Python 三重循环是 \(1.25\times10^7\) 次迭代（约 10 秒），必须把最内层下沉。
做法：把 f 存成「每个 \(t\) 一行、行内是 \(h\) 维」的二维列表，内层整行批处理：
# [片段]
for t in range(T, ti - 1, -1): # 外层 t 倒序，第一维照样是 01 语义
src = f[t - ti] # 倒序保证这一行还是旧值
cand = [x + a for x in src[:H + 1 - hi]] # 第二维的平移由切片起点 hi 承担
row = f[t] # 绑成局部名，避免下一句两次下标取行
row[hi:] = list(map(max, row[hi:], cand)) # 整行一次取 max，第二维的循环消失
这样 Python 层只剩 \(n \times T = 2.5\times10^4\) 次循环， 内层 \(1.25\times10^7\) 次元素操作全在 C 层，实测 1 秒出头。
坑：外层 \(t\) 必须倒序。正序会让
f[t - ti]已含本物品，退化成完全背包。
题解：solutions/nowcoder/BISHI139/sol.py（已通过官方样例验证）
7 分组背包¶
物品分成若干组，同一组内至多选一件。
循环顺序是唯一的考点¶
# [片段]
for 每一组: # 组在最外层：一组处理完 f 才整体推进一次
for 容量 c 倒序: # 倒序 ⇒ f[c - v_i] 仍是「本组开始前」的值
for 组内每件物品 i: # 物品在最内层，同一个 c 上多件物品互相竞争
f[c] = max(f[c], f[c - v_i] + w_i) # 只有一件能最终留在 f[c] 上
「组」在最外层、「物品」在最内层。 含义是：处理完一整组后 f 才更新一次，
所以组内所有物品的候选都来自「上一组结束时」的 f，天然保证至多选一件。
写成「物品在外、容量在内」就退化成普通 01 背包（一组能选多件）。 这是分组背包唯一会写错的地方。
Python 写法：每组一个临时数组¶
# [片段]
for group in groups:
tmp = f[:] # 这一组什么都不选：先原样复制一份做基准
for v, w in group:
cand = [x + w for x in f[:M + 1 - v]] # ★ 候选一律来自旧的 f，不是 tmp
tmp[v:] = list(map(max, tmp[v:], cand)) # 结果累积在 tmp 上，组内取最优的一件
f = tmp # 整组处理完才切换，保证组内至多选一件
候选取自 f（旧的）而不是 tmp（本组已选过的），组内互斥就成立了；
同时内层全走 C 层，Python 层循环只有物品数那么多次。
题解：solutions/nowcoder/BISHI140/sol.py（已通过官方样例验证）
8 依赖背包¶
「依赖」有两种，方向不同，做法完全不同，这是最容易混的地方。
| 类型 | 关系 | 结构 | 做法 |
|---|---|---|---|
| 双向依赖 | 买 \(u\) 必须买 \(v\)，买 \(v\) 也必须买 \(u\) | 等价关系 ⇒ 若干个连通块 | 并查集缩点，退化成裸 01 背包 |
| 单向依赖 | 买子必须买父 | 树 / 森林 | 树上分组背包 |
BISHI103：双向依赖 ⇒ 并查集缩点¶
\(n \le 10^4\) 朵云、\(m \le 5\times10^3\) 个搭配、\(w \le 10^4\) 元。
「必须一起买」是等价关系，用并查集把互相牵连的云朵缩成一个「超级物品」 （价格 = 组内之和，价值 = 组内之和），之后就是最普通的 01 背包：整组买或不买。
最坏 \(O(\text{组数} \times w) = 10^8\)，C++ 刚好，Python 逐格循环绝对跑不动。
solutions/nowcoder/BISHI103/sol.py 上了四条优化：
- 整段切片 + zip 代替内层 for（C 层）
- 同价剪枝：价格为 \(c\) 的组最多买 \(\lfloor w/c \rfloor\) 个，按交换论证只留价值最大的那些
- 相同 (价格, 价值) 去重 + 二进制拆分：把 \(k\) 个完全一样的组合成 \(O(\log k)\) 个打包物品
- 按价格升序处理 + dp 数组按
reach动态增长
⚠️ 即便如此，极端数据（\(10^4\) 个价格互不相同的组 + \(w = 10^4\)）仍约 6.5 秒， 是 \(9\times10^7\) 次元素级运算在纯 CPython 的物理下限。 而「大量同款廉价组」这类数据经优化后从 4.2 秒降到 0.06 秒。 题解 docstring 里如实记录了这个限制。
顺带一个真 bug 的教训：
reach上界截断优化最初会让dp[reach+1..w]残留旧值 （应继承dp[reach]），导致答案偏小。官方样例是过的，靠随机对拍才暴露。⚠️ BISHI103 必须用 PyPy3 提交。 缩点后是 \(10^4\) 件物品 \(\times\) \(10^4\) 容量的 0/1 背包，即使已经上了「同价剪枝 + 去重 + 二进制拆分 + reach 动态增长」四条优化， 极端数据下仍是 \(10^8\) 级的元素操作，CPython 实测 4.3 秒（时限 2 秒）。 内层已经是最快写法——实测
map(max, ...)反而比列表推导式慢一倍， 因为max()每个元素都要走一次 Python 函数调用。顺带记一条实测结论：牛客判题机没有装 numpy （提交
import numpy直接ModuleNotFoundError）， 所以「上 numpy 向量化」这条路在牛客上是走不通的。提交语言登记在该题
meta.json的langs.py.submitLang字段。
题解：solutions/nowcoder/BISHI103/sol.py（已通过判题机验证，PyPy3）
BISHI142：单向依赖 ⇒ 树上分组背包¶
选恰好 \(M\) 门课，选一门必须选它的全部先修课，求最大学分。\(N, M \le 300\)。
每门课至多一个直接先修课 ⇒ 先修关系构成森林。加一个编号 0 的虚拟根（学分 0） 把森林接成一棵树，问题变成「在树上选 \(M+1\) 个点（含虚拟根）， 且选中点集对父亲封闭，求最大权和」。
初值 \(f[u][1] = s_u\)，然后逐个合并孩子：
合并的本质就是分组背包：每个孩子是一组，组内选项是「从这个孩子的子树里拿 \(t\) 个点」。 所以合并时要「先复制一份旧的 \(f[u]\) 再倒着更新」。
复杂度：经典结论是「每对点只在它们的 LCA 处被合并一次」，总合并量 \(O(N^2)\)， \(N = 300\) 时不到 \(9\times10^4\)。
坑： 1. 目标是 \(f[0][M+1]\)——虚拟根占一个名额； 2. \(t\) 的上界要同时被「孩子子树大小」和 \(M+1\) 截断，否则退化成 \(O(NM^2)\)； 3. 先修链可能深到 300，用迭代式后序遍历（虽然 300 层递归安全，但迭代是通用姿势）。
题解：solutions/nowcoder/BISHI142/sol.py（已通过官方样例验证）
泛化物品¶
前面几节的物品各有各的形状：01 背包的一件物品只有「选 / 不选」两种代价， 分组背包一组里最多选一件，依赖背包则是一棵树。 泛化物品把它们统一成同一样东西—— 一件泛化物品不是「体积 \(v\)、价值 \(w\)」这样一对数，而是一个从费用到价值的函数 \(h(c)\)： 在这件物品上花费 \(c\) 的代价，能得到的最大价值就是 \(h(c)\)。
这样一来前面所有的物品都只是它的特例：
| 原来的形状 | 写成泛化物品 |
|---|---|
| 01 背包的一件物品 | 只在 \(c = 0\) 与 \(c = v\) 两处有定义，取值 \(0\) 与 \(w\) |
| 完全背包的一件物品 | 在 \(c = kv\) 处取 \(kw\) |
| 分组背包的一整组 | \(h(c)\) ＝ 该组内所有物品在费用 \(c\) 下的最大价值 |
| 依赖背包的一棵子树 | \(h(c)\) ＝ 这棵子树花费 \(c\) 时的最优价值 |
两件泛化物品的「和」定义为：把总费用在两者之间任意分配后取最优。
这个式子正是分组背包与树上背包内层那一重循环在做的事， 只是那里写成了对数组下标的枚举。合并两件泛化物品的代价是 \(O(V^2)\)， \(n\) 件依次合并就是 \(O(nV^2)\)；物品形状规整时（比如 01 背包的两点函数） 这一重枚举退化成常数，也就回到了熟悉的 \(O(nV)\)。
把物品看成函数之后，背包问题本身也成了一件泛化物品： \(f[c]\) 就是「全部物品合起来那件泛化物品」的函数值， 求 \(f[V]\) 无非是把所有泛化物品加起来再取一个点。 这个视角在两处派得上用场：一是树上背包的合并顺序（子树逐个加到父节点上）， 二是某一组物品的代价规律根本没法用「体积 ＋ 价值」描述时—— 只要写得出 \(h(c)\)，它就能进这个框架，动态规划的转移式一个字都不用改。
9 「至少装满」型¶
BISHI141 是一个很好的变式：容量维不是「不超过」而是「至少」。
选若干煤炭烧完 \(m\) 单位矿石，至多对一枚施魔法（耗时减半），求最短总时间。 保证 \(n \cdot m \le 10^6\)。
把容量维当成「已融化的矿石量」，超过 \(m\) 的部分一律并到 \(m\) 这一格。 实现方式就是把 \(j - v\) 换成 \(\max(0,\ j - v)\)——剩余需求不会变成负数， 多融化的部分不额外记账。
再加一维 0/1 表示魔法是否用过：
Python 写法：把「平移 + 加常数 + 取 min」写成一次批处理：
# [片段]
def shift(d, cap, cost, m):
"""返回数组 g，g[j] = d[max(0, j-cap)] + cost。"""
# 前 cap 项的 j-cap 都是负数，被 max(0, ...) 夹到 0，所以统一取 d[0]
# 其余部分就是把 d 整体右移 cap 位再加上 cost，切片长度正好补满到 m
return [d[0] + cost] * cap + [x + cost for x in d[:m + 1 - cap]]
坑：\(f_1\) 的三个来源必须先全部用旧值算好再一起赋值， 否则会出现「一次操作里用了两次魔法」。
题解：solutions/nowcoder/BISHI141/sol.py（已通过官方样例验证）
10 方案数与具体方案¶
求方案数¶
把 \(\max\) 换成 \(+\)，初值 \(f[0] = 1\)：
# [片段]
f = [0] * (V + 1)
f[0] = 1 # 「什么都不装」算一种方案，是计数的递推起点
for v, w in items: # 01 背包：倒序 / 整段加
tail = V + 1 - v
# zip 的两个切片都取自旧的 f：a 是「不选这件」，b 是「选这件」，两类不重不漏
f[v:] = [(a + b) % MOD for a, b in zip(f[v:], f[:tail])]
注意语义：这里数的是「体积恰好为 \(c\) 的方案数」。 若要数「最优价值的方案数」，需要同时维护 \(f[c]\)（最优值）和 \(g[c]\)（达到最优值的方案数）， 转移时比较大小：更优则覆盖 \(g\)，相等则累加 \(g\)。
最优方案总数¶
上面数的是「体积恰好为 \(c\) 的方案数」。另一类常见问法是最优方案总数—— 在所有能取到最大价值的方案里，一共有多少种。
做法是让最优值与计数同步递推：\(f[c]\) 记最优价值、\(g[c]\) 记达到 \(f[c]\) 的方案数， 每次转移把候选值与当前值比一下：
# [片段]
f = [0] * (V + 1) # f[c] = 费用恰为 c 时的最优价值
g = [0] * (V + 1); g[0] = 1 # g[c] = 取到 f[c] 的方案数；空方案是计数的起点
for v, w in items: # 01 背包：倒序，保证 f[c-v] 还是「上一轮」的值
for c in range(V, v - 1, -1):
cand = f[c - v] + w
if cand > f[c]: # 找到更优的价值：方案数整个换成新来源的
f[c], g[c] = cand, g[c - v]
elif cand == f[c]: # 打平：两个来源的方案都算数，累加
g[c] = (g[c] + g[c - v]) % MOD
三处容易写错：
g的初值只有g[0] = 1，其余全是 \(0\)。把g整个填成 \(1\)， 等于承认每个费用上都凭空存在一个方案。- 「更优」与「打平」必须分开处理：更优时是覆盖，打平时才是累加。 写成一律累加会把次优方案也数进去。
- 若题面问的是「价值等于最大值的方案数」而不限定费用， 最后要把所有 \(f[c]\) 达到全局最大的位置上的 \(g[c]\) 加起来，而不是只取 \(g[V]\)—— 不要求装满时，最优值未必出现在 \(c = V\) 处。
复杂度与原背包同阶：多出来的只是一个同规模的计数数组，\(O(nV)\) 时间、\(O(V)\) 空间。
输出具体方案¶
一维滚动数组丢失了「第几件物品」的信息，无法回溯。两种办法：
| 办法 | 空间 | 做法 |
|---|---|---|
| 保留二维 \(f[i][c]\) | \(O(nV)\) | 从 \(f[n][V]\) 倒推：若 \(f[i][c] = f[i-1][c]\) 则第 \(i\) 件没选，否则选了 |
| 记录选择标记 | \(O(nV)\) 位 | 转移时记下 choose[i][c] = True/False |
字典序最小的方案：把物品倒序编号做 DP，回溯时从第 1 件开始贪心地「能选就选」。
11 不是背包的「背包题」¶
BISHI44「灵异背包？」 是一个提醒：题目名带「背包」不代表要写背包。
选出若干数，和为偶数且最大。\(n \le 10^5\)，\(a_i \le 2\times10^4\)。
\(O(n \cdot S)\) 的背包 DP 是 \(2\times10^9\)，必挂。正解是奇偶性 + 贪心：
- 先全选，总和 \(S\)（显然是上界）；
- \(S\) 为偶数 ⇒ 直接输出 \(S\)；
- \(S\) 为奇数 ⇒ 奇数元素的个数必为奇数，必须扔掉奇数个「奇数」。扔得越少越好， 所以只扔一个，且扔最小的那个奇数，答案 \(= S - \min_{\text{odd}}\)。
扔偶数元素改变不了奇偶性，只会让和变小，不考虑。\(O(n)\) 一遍扫完。
识别信号：看到「和为偶数」「异或为 0」「模 \(k\) 余 \(r\)」这类条件， 先想想能不能用奇偶性 / 同余的结构直接构造，而不是把它当成背包的一维。
题解：solutions/nowcoder/BISHI44/sol.py（已通过官方样例验证）
12 例题¶
| 题号 | 题名 | 难度 | 题解 |
|---|---|---|---|
| BISHI136 | 【模板】01背包 | 简单 | 题解 |
| BISHI137 | 【模板】完全背包 | 中等 | 题解 |
| BISHI138 | 【模板】多重背包 | 中等 | 题解 |
| BISHI139 | 【模板】二维费用背包 | 中等 | 题解 |
| BISHI140 | 【模板】分组背包 | 较难 | 题解 |
| BISHI103 | 【模板】有依赖的背包问题 | 中等 | 题解 |
| BISHI141 | 来硬的 | 较难 | 题解 |
| BISHI142 | 最大学分 | 较难 | 题解 |
| BISHI44 | 灵异背包？ | 简单 | 题解 |
| BM70 | 兑换零钱(一) | 中等 | 题解 |
| LC139 | 单词拆分 | 中等 | 题解 |
| LC279 | 完全平方数 | 中等 | 题解 |
| LC322 | 零钱兑换 | 中等 | 题解 |
| LC416 | 分割等和子集 | 中等 | 题解 |
另一处题库里的四道背包题¶
LC 322. 零钱兑换与兑换零钱(一)是同一道题：完全背包求「最少件数」， 初值填正无穷、\(f[0] = 0\)，容量正序循环，凑不出时值仍为无穷，返回 \(-1\)。 LC 279. 完全平方数 是同一份代码换一套物品：物品取 \(1^2, 2^2, \dots, \lfloor\sqrt n\rfloor^2\)， 物品数 \(O(\sqrt n)\)，整体 \(O(n \sqrt n)\)，\(n \le 10^4\) 时轻松。
LC 416. 分割等和子集：01 背包的可行性版本。
总和为奇数直接无解；否则问「能否恰好凑出总和的一半」，
状态退化成布尔值，容量倒序循环，\(O(n \cdot \text{sum})\)。
布尔背包在 Python 里还有一条整数位图的路——
拿一个大整数当位集合，mask |= mask << v 一次完成整轮转移，
移位与或运算都在 C 层，比逐格循环少一个数量级的解释开销。
LC 139. 单词拆分：完全背包，只是物品的「体积」不固定在一个数上。 状态是「前 \(i\) 个字符能否被拆完」，转移枚举最后一段的起点 \(j\)， 要求 \(f[j]\) 为真且 \(s[j:i]\) 在词典里。 它之所以算完全背包，是因为同一个单词可以重复使用，且拼接顺序不影响可行性。 串长为 \(n\)、词典中最长单词长为 \(L\) 时，只需枚举 \(i - L \le j < i\)，\(O(nL)\)。 不设这个下界会退化成 \(O(n^2)\)；\(n \le 300\) 的规模下两者都能过， 但下界这一步说明的是「物品体积有上界」这条信息该怎么用。
13 本章速查¶
| 形态 | 容量循环 | 关键点 |
|---|---|---|
| 01 背包 | 倒序 | 用「上一轮」的值 |
| 完全背包 | 正序 | 用「本轮」的值；Python 改二进制倍增 |
| 多重背包 | 倒序 | 二进制拆分；先截断 \(s \leftarrow \min(s, m/v)\)；特判 \(v=0\) |
| 混合背包 | 倒序 | 统一转成 01 物品 |
| 二维费用 | 两维都倒序 | 内层整行批处理 |
| 分组背包 | 组在外、物品在内 | 候选一律取自旧 f |
| 双向依赖 | 倒序 | 并查集缩点 ⇒ 裸 01 背包 |
| 单向依赖 | — | 树上分组背包，\(t\) 双重截断 |
| 至少装满 | 倒序 | \(j-v\) 换成 \(\max(0, j-v)\) |
| 初值 | 含义 |
|---|---|
| 全 0 | 不要求装满 |
f[0]=0，其余 \(-10^{18}\) |
恰好装满（不要用 -1） |
f[0]=1，其余 0 |
方案计数 |
| Python 要点 | 写法 |
|---|---|
| 01 背包整段取 max | f[v:] = list(map(max, f[v:], [x+w for x in f[:V+1-v]])) |
| 完全背包 | 二进制倍增，每轮做一次上面的整段取 max |
| 为什么能这样写 | 候选数组在赋值前用旧 f 算好，01 语义自动成立 |
| 提速 | 比 Python 层循环快 5–8 倍 |
| 单调队列优化多重背包 | \(O(nm)\)，极限数据实测比二进制拆分快 5.4 倍；复杂度优先于常数 |
| 语言劣势题 | BISHI103 / BISHI138 CPython 必超时，登记为 PyPy3 提交；BISHI137 随机数据偏险 |