01 / 本课学习路线
本课学习路线
阅读与推演约 110 分钟，练习约 67 分钟，进阶练习另需约 50 分钟
02 / 学习目标与先修自测
学完本课你能做什么，以及开始前需要会什么
本课只多一件事：内层循环的方向。它由「转移读的是旧值还是新值」决定，和上一课的滚动数组是同一个问题。
| 学完后能做的事 | 正文位置 | 检查方式 |
|---|---|---|
| 不看笔记解释容量倒序遍历的原因 | 第 04 节 | 自查第 2 条 |
| 用单物品反例自测背包的遍历方向 | 第 04、09 节 | 自查第 3 条、练习 4 |
| 说出「恰好装满」与「不超过」在初始化上的差别 | 第 03、07 节 | 自查第 4 条、练习 3 |
| w=0、超预算、价值为 0 三类特殊物品都有明确处理 | 第 05 节 | 自查第 5 条 |
| 识别不同场景下的背包模型（显存、块、人数），通过 AI017、P3415 | 第 05、06、08 节 | 必做任务 1、2 |
先修自测：下面 5 题请先自己写答案，再展开对照。答不出的按括号里的位置补看再回来。本课假定你已完成上一课「网格动态规划与空间优化」。
| 题号 | 题目 | 补看位置 |
|---|---|---|
| 自测 1 | range(5, 1, -1) 依次产生哪些数？要产生 5..2 之外还包含 2 本身，下界该写几？ | for 循环 |
| 自测 2 | 600 字节按 512 字节一块占几块？用整数运算写出向上取整。 | 数字与运算符 |
| 自测 3 | [x + 7 for x in dp] 得到什么？它和 for c in range(len(dp)): dp[c] += 7 结果一样吗？ | 列表常用操作 |
| 自测 4 | 一行 5,4,2,3 怎样读成整数列表？ | 标准输入输出与首次独立提交 |
| 自测 5 | 上一课滚动数组里，更新到 dp[j] 时 dp[j-1] 是旧值还是新值？ | 网格动态规划与空间优化第 05 节 |
展开先修自测答案
自测 1：5、4、3、2（不含下界 1）。要包含 2，下界写 1，也就是 range(cap, w - 1, -1) 里 w - 1 的来历：容量要一直取到 w 本身。
自测 2：2 块。(600 + 511) // 512 = 2；一般写法 (size + 511) // 512，不要用浮点除法再取整。
自测 3：一个新列表，每项加 7；两种写法结果相同。AI017 里 w = 0 的模型就是「对所有容量加收益」。
自测 4：[int(x) for x in input().split(",")]。P3409 的第一行正是逗号分隔。
自测 5：新值（本行刚更新）。背包转移要读的 dp[c-w] 必须是旧值（没放本物品），所以内层要倒过来走。
03 / 概念与术语
物品、容量、价值；0/1 与完全；恰好装满与不超过
背包题的三样东西是物品（每件一个重量、一个价值）、容量（重量之和的上限）、目标（价值之和最大，或方案数）。识别出这三样，题目场景就不重要了。
| 术语 | 含义 | 代码里的位置 |
|---|---|---|
| 物品 (w, v) | 重量 w 占容量，价值 v 是要最大化的量；两者单位可以不同（块 / 字节） | 读入后的列表 |
| 容量 cap | 重量之和的上限 | dp = [0] * (cap + 1) |
| 0/1 背包 | 每件物品至多选一次 | 内层容量倒序 |
| 完全背包 | 每件物品可选任意次 | 内层容量正序（练习 2） |
| 不超过 | 重量之和 ≤ cap，求最大价值 | 全 0 初始化，答案 dp[cap] |
| 恰好装满 | 重量之和 = cap | dp[0] = 0（或 1），其余不可达（最值用负无穷，计数用 0） |
| 旧值 / 新值 | dp[c-w] 必须是没放本物品时的值 | 倒序保证读到旧值 |
补充学习（选学）双资源背包：为什么只倒序一维会错约 5 分钟AI025 的一维解法只能通过部分用例
AI025 同时限制显存 W 和算力 C：dp[w][c] 是二维费用，转移对两个维度都做 max(dp[w][c], dp[w-wi][c-ci] + v)，两层容量循环都从大到小。为什么两维都要倒序：AI025 的题面允许某件物品的某一维需求为 0。设一件物品 (w_i, c_i, v) = (0, 1, 1)、W = C = 2，只把显存维倒序、算力维升序时，w - w_i 就是同一行 w，算力维读到的正是本轮刚写进去的新值，这件物品被计入两次，答案得 2；两维都倒序得 1，才是正确答案。反过来说，如果所有物品两维需求都大于 0，只倒序一维在这类单件例子上也能算对（单件 (1,1,1)、W = C = 2 两种写法都得 1）——所以不能笼统地说「只倒序一维就一定重复」，真正的分界是有没有某一维为 0 的物品。既然题面允许 0，实现就按两维都倒序写，这是对全部输入都安全的写法。
只考虑显存的一维解法无法覆盖算力约束，因此只能通过部分用例：例如显存 150、算力 5 下三件 (1,5,10)(1,3,6)(1,2,5) 的正确答案是 11（选后两件），忽略算力会得到 21。O(n·W·C) = 80×150×150 = 1.8×10⁶，这个规模允许直接做二维费用动态规划；实现时要同时检查状态定义、初始化，以及两个资源维度都倒序更新。
补充学习（选学）按块分配：单位换算的易错点约 4 分钟两个 300 字节的文件，为什么装不进 1 块的剩余空间
P3415 中一个块只能分配给一个文件：两个 300 字节的文件各占 1 块（512 B），共需 2 块，不能按总字节数 600 B 合并计算。按字节累加会高估剩余空间，大规模数据下答案系统性偏大。换算公式 ceil(size/512) = (size + 511) // 512，容量 1474560 // 512 = 2880 块。
背包的价值仍是文件字节数（要最大化的量），重量是占用的块数。价值和重量分别换算、分别使用，不要全部换成块。
04 / 五要素与倒序
用一张表理解倒序，用一组反例检验它
五要素：① dp[c] = 容量不超过 c 时的最大价值；② 对每件 (w, v)，dp[c] = max(dp[c], dp[c-w] + v)；③ 全 0；④ 外层逐件物品（顺序任意）、内层容量从容量上限（cap）降到 w；⑤ dp[cap]。
| 处理完 | dp[0..5] | 解释 |
|---|---|---|
| (2,3) | 0 0 3 3 3 3 | 容量 ≥ 2 都能放它 |
| (3,4) | 0 0 3 4 4 7 | dp[5] = max(3, dp[2]+4) = 7 |
| (4,5) | 0 0 3 4 5 7 | dp[4] = max(4, dp[0]+5) = 5；答案 dp[5] = 7，选 (2,3)+(3,4) |
每一行的转移读取的都是上一行（旧值）：倒序遍历在一维数组上模拟出了这个效果。
正序反例：单物品 (2,3)、容量 4
正序 dp = [0, 0, 3, 3, 6] ← dp[4] = dp[2](本轮新值) + 3 = 6，物品被选了两次 倒序 dp = [0, 0, 3, 3, 3] ✓ 一件物品最多贡献一次 对照记忆：完全背包（物品可重复选）正好用正序——遍历方向决定了物品能否重复选取 预算 10、两件 (3,7)(4,5)：0/1 正确答案 12，正序会得到 21（三个 (3,7)）
「恰好装满」与「不超过」的初始化不同
「不超过容量求最大价值」全 0 初始化即可；「恰好装满」（如 P3409 恰好坐满）要求 dp[0] 合法、其余标为不可达（求最值用 -∞，计数用 0）。求最值时全 0 初始化会把无法恰好装满的状态当成合法起点，答案偏大；计数版的错误在另一头——漏写 dp[0] = 1，「一个团都不上」这个起点没登记，全表始终是 0（第 07 节）。第 10 节练习 3 用容量 5、两件 (2,3)(4,5) 对照两种问法。
从空文件写模板：倒序转移
Python# 请补全以下 0/1 背包练习模板，并按题目定义处理重量为 0 的物品
import sys
def solve() -> None:
data = sys.stdin.read().split()
n, cap = int(data[0]), int(data[1])
items = [] # 待完成 1：读入 (w, v)；题目单位若是「块」，先 ceil(size/512) 换算
dp = [0] * (cap + 1)
for w, v in items:
# 待完成 2：w == 0 的物品如何处理（AI017：直接给所有容量加收益）
for c in range(cap, w - 1, -1): # 容量从大到小更新：避免同一物品在一轮内被重复选取
pass # 待完成 3：写出转移
print(dp[cap])
solve()AI017 的 w=0 物品可以在主循环外先把收益累加为一个常数（对所有容量都成立），也可以让 range(cap, -1, -1) 自然覆盖。两种都正确，选一种自己想清楚的。
05 / AI017 显存装箱
题面示例逐件表；w=0、超预算、价值 0 三类物品
AI017「显存装箱」：第一行 n 与显存预算 C（1 ≤ n ≤ 300，0 ≤ C ≤ 30000），随后 n 行每行 w_i v_i（0 ≤ w_i ≤ 30000，0 ≤ v_i ≤ 10000）；每个模型至多部署一份，显存之和不超过 C，输出最大总收益。题面示例 1：预算 10，(3,4)(4,5)(5,6)(2,3) → 13；示例 2：预算 5，(0,7)(6,9)(5,4) → 11。
| 处理完 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| (3,4) | 0 | 0 | 0 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |
| (4,5) | 0 | 0 | 0 | 4 | 5 | 5 | 5 | 9 | 9 | 9 | 9 |
| (5,6) | 0 | 0 | 0 | 4 | 5 | 6 | 6 | 9 | 10 | 11 | 11 |
| (2,3) | 0 | 0 | 3 | 4 | 5 | 7 | 8 | 9 | 10 | 12 | 13 |
答案 dp[10] = 13：(3,4) + (5,6) + (2,3)，显存 10。最后一行 dp[9] = max(11, dp[7] + 3 = 12) = 12、dp[10] = max(11, dp[8] + 3 = 13) = 13，读的 dp[7]、dp[8] 都是上一行的值。
| 物品 | 处理 | 示例 |
|---|---|---|
| w = 0 且 v > 0 | 对所有容量无条件加 v（dp = [x + v for x in dp]），或让 range(cap, -1, -1) 自然覆盖 | 示例 2 的 (0,7)：预算 5 → 7 + 4 = 11；预算 0、(0,5)(0,3)(2,9) → 8 |
| w > cap | range(cap, w - 1, -1) 为空，自然跳过 | 示例 2 的 (6,9) |
| v = 0 | 放不放都一样，可跳过也可照常处理 | (3,0)(3,7)(4,0)(4,6)、预算 10 → 13 |
06 / P3415 按块占用的软盘
重量是块数、价值是字节数；向上取整
P3415「通过软盘拷贝文件」：第一行文件数 n，随后 n 个整数是各文件的字节数；软盘容量 1474560 字节、按 512 字节一块分配、一块只能给一个文件；输出能拷入的文件总字节数的最大值。题面没有给示例，下面的数字是本课自己算的。
| 输入 | 换算 | 输出 |
|---|---|---|
| 3 个文件：1000000、500000、400000 | 块数 1954 + 977 + 782 = 3713 > 2880，只能选两个 | 1400000（第 1、3 个：1954 + 782 = 2736 块；前两个要 2931 块，放不下） |
| 2 个文件：1474560、1 | 2880 块 + 1 块 | 1474560 |
| 1 个文件：1474561 | ceil = 2881 块 > 2880 | 0 |
| 4 个文件：300、300、1473536、1000 | 1 + 1 + 2878 + 2 块 | 1474536（第 3、4 个：2878 + 2 = 2880 块；前三个也是 2880 块，但只有 1474136 字节） |
| 3 个文件：300、300、1473800 | 1 + 1 + 2879 块 | 1474100（1473800 占 2879 块，只剩 1 块，两个 300 只能放一个） |
最后一组：1473800 字节要占 2879 块，最后一块用了 264 字节，剩下的 248 字节不能再给别的文件；两个 300 字节的文件各要一整块，只剩 1 个完整空块就只能放一个——这就是「一块只能给一个文件」。按字节累加会以为 300 + 300 + 1473800 = 1474400 ≤ 1474560 全放得下。
按字节做容量会怎样：2000 个 513 字节的文件，按块每个占 2 块（1024 字节），最多放 1440 个、总计 738720 字节；按字节累加会以为 2000 个全放得下（1026000 字节 ≤ 1474560），答案系统性偏大。
07 / 方案计数与双资源
P3409：取最大值换成加法、dp[0] = 1；AI025：两个容量维度都倒序
P3409「代表团坐车」：第一行各代表团人数（逗号分隔，团数 < 30、每团 < 30 人），第二行汽车容量（< 100）；一个团只能整体上一辆车，求恰好坐满的方案数，无解输出 0。题面示例：5,4,2,3,2,4,9 / 10 → 4；1,2,3,4 / 3 → 2。
| 处理完 | dp[0] | dp[1] | dp[2] | dp[3] |
|---|---|---|---|---|
| 初始 | 1 | 0 | 0 | 0 |
| 1 人团 | 1 | 1 | 0 | 0 |
| 2 人团 | 1 | 1 | 1 | 1（1+2） |
| 3 人团 | 1 | 1 | 1 | 2（+ 单独 3） |
| 4 人团 | 1 | 1 | 1 | 2 |
dp[0] = 1 是「什么都不选」这一种方案，是所有方案计数的起点；写成 0 时全表都是 0。示例 1 处理完 7 个团后 dp[10] = 4：[2,3,5]、[2,4,4] 各按两个不同的 2 人团 / 4 人团算两次。
AI025「双资源模型部署」：第一行 n W C（n ≤ 80，W、C ≤ 150），随后 n 行 w_i c_i v_i；两个维度分别不超过预算，求最大收益。题面示例 1：W = C = 10，(5,3,60)(4,6,40)(6,6,50) → 100；示例 2：W = C = 5，(0,0,7)(5,5,9)(3,2,4) → 16。状态 dp[i][j] 是二维容量，转移仍是「放或不放」，两层容量循环都倒序；任一维超预算的物品直接跳过。
08 / 从五要素到程序
四道题的完整参考程序，每一步落在哪几行
先自己写完并提交一次，再展开对照。
| 要素 | AI017 | P3415 | P3409 | AI025 |
|---|---|---|---|---|
| ① 状态 | dp[c] 显存 ≤ c 的最大收益 | dp[b] ≤ b 块的最大字节数 | dp[c] 恰好 c 人的方案数 | dp[i][j] 显存 ≤ i、算力 ≤ j 的最大收益 |
| ② 转移 | max(不放, dp[c-w] + v) | max(不放, dp[b-blocks] + size) | dp[c] += dp[c-p] | max(不放, dp[i-w][j-c] + v) |
| ③ 初始化 | 全 0 | 全 0 | dp[0] = 1 | 全 0 |
| ④ 遍历顺序 | 容量倒序 | 块数倒序 | 人数倒序 | 两维都倒序 |
| ⑤ 答案位置 | dp[C] | dp[2880] | dp[cap] | dp[W][C] |
展开完整参考程序 1：AI017 显存装箱（先自己写完并提交一次，再展开对照）
完整程序：AI017（标准输入 → 标准输出）
Pythonimport sys
data = sys.stdin.read().split()
n, cap = int(data[0]), int(data[1])
dp = [0] * (cap + 1) # ① dp[c] = 显存不超过 c 时的最大收益；③ 全 0（什么都不部署）
for k in range(n): # ④ 外层：逐个模型，顺序任意
w, v = int(data[2 + 2 * k]), int(data[3 + 2 * k])
if w == 0: # 不占显存的模型：对每个容量都无条件加上收益
for c in range(cap + 1):
dp[c] += v
continue
for c in range(cap, w - 1, -1): # ④ 内层：容量从大到小，保证 dp[c - w] 还是「没放本模型」的旧值
if dp[c - w] + v > dp[c]: # ② 放或不放取较大者
dp[c] = dp[c - w] + v
print(dp[cap]) # ⑤ 预算上限处自测建议：题面两组示例（13 / 11）、单物品反例 1 4 / 2 3（3）、预算 0 且含 w=0（8）、容量恰好等于 w（999）。n = 300、C = 30000 时约 9×10⁶ 次内层循环，内层只做数组读写和比较。
展开完整参考程序 2：P3415 通过软盘拷贝文件
完整程序：P3415（标准输入 → 标准输出）
Pythonimport sys
data = sys.stdin.read().split()
n = int(data[0])
sizes = [int(x) for x in data[1:1 + n]] # 每个文件的字节数
CAP = 1474560 // 512 # 软盘共 2880 块
dp = [0] * (CAP + 1) # ① dp[b] = 用不超过 b 块时能装下的最大总字节数
for size in sizes:
blocks = (size + 511) // 512 # 重量：向上取整的块数
for b in range(CAP, blocks - 1, -1): # ④ 块数倒序
if dp[b - blocks] + size > dp[b]: # ② 价值仍是字节数
dp[b] = dp[b - blocks] + size
print(dp[CAP])自测建议：第 06 节的几组用例（1400000、1474560、0、1474536、1474100）；题目页参考题解（Java / C / Go）用同一模型。
展开完整参考程序 3：P3409 代表团坐车（进阶练习）
完整程序：P3409（标准输入 → 标准输出）
Pythonimport sys
people = [int(x) for x in sys.stdin.readline().strip().split(",")] # 第一行：各代表团人数，逗号分隔
cap = int(sys.stdin.readline().strip()) # 第二行：汽车容量
dp = [0] * (cap + 1) # ① dp[c] = 恰好坐 c 人的方案数
dp[0] = 1 # ③ 一个团都不上：恰好 0 人，算 1 种
for p in people:
for c in range(cap, p - 1, -1): # ④ 倒序：每个团至多上一次
dp[c] += dp[c - p] # ② 计数：不选 + 选（本团上车前恰好 c - p 人）
print(dp[cap]) # ⑤ 恰好坐满自测建议：题面示例（4 / 2）、无解 5,5 / 3（0）。
展开完整参考程序 4：AI025 双资源模型部署（进阶练习）
完整程序：AI025（标准输入 → 标准输出）
Pythonimport sys
data = sys.stdin.read().split()
n, W, C = int(data[0]), int(data[1]), int(data[2])
dp = [[0] * (C + 1) for _ in range(W + 1)] # ① dp[w][c] = 显存不超过 w、算力不超过 c 时的最大收益
for k in range(n):
w, c, v = int(data[3 + 3 * k]), int(data[4 + 3 * k]), int(data[5 + 3 * k])
if w > W or c > C: # 任一维超预算：不可能部署
continue
for i in range(W, w - 1, -1): # ④ 两个维度都倒序
for j in range(C, c - 1, -1):
if dp[i - w][j - c] + v > dp[i][j]: # ② 放或不放；w 或 c 为 0 时读到的仍是本模型放入前的值——因为该维倒序
dp[i][j] = dp[i - w][j - c] + v
print(dp[W][C])自测建议：题面两组示例（100 / 16）、第 09 节只倒序一维会错的 1 2 2 / 0 1 1（1）与忽略算力维会错的例子（11）。
09 / 边界、反例与复杂度
错误做法在具体输入上各输出什么
下面每一行都是一个具体的错误程序，给出输入、错误输出与正确输出；把参考程序改成对应写法就能复现。
| 错误做法 | 输入 | 错误输出 | 正确输出 | 判题结果 |
|---|---|---|---|---|
| AI017 容量正序 | 预算 4、单件 (2,3) | 6 | 3 | 答案错误（WA） |
| AI017 容量正序 | 题面示例 1 | 15 | 13 | 答案错误（WA） |
| AI017 w = 0 的模型被当作放不下而跳过 | 题面示例 2 | 4 | 11 | 答案错误（WA） |
| AI017 倒序下界写成 w（漏掉容量恰好等于 w） | 预算 128、(128,999)(129,10000)(64,500) | 500 | 999 | 答案错误（WA） |
| P3415 块数向下取整 | 1 个文件 1474561 字节 | 1474561 | 0 | 答案错误（WA） |
| P3409 dp[0] 写 0 | 题面示例 1 | 0 | 4 | 答案错误（WA） |
| P3409 容量正序（每个团可重复上车） | 题面示例 1 | 28 | 4 | 答案错误（WA） |
| P3409 第一行按空格拆 | 题面示例 1 | 抛出 ValueError | 4 | 运行错误（RE） |
| AI025 忽略算力维 | 显存 150、算力 5、(1,5,10)(1,3,6)(1,2,5) | 21 | 11 | 答案错误（WA） |
| AI025 算力维正序 | W = C = 2、单件 (0,1,1) | 2 | 1 | 答案错误（WA） |
第二行：正序时同一个模型被反复计入，示例 1 变成五份 (2,3)（显存 10、收益 15）。第七行的 28：同一个团可以上多次时，恰好 10 人的组合数变成 28。
| 做法 | 时间 | 空间 | 本课规模下 |
|---|---|---|---|
| 一维 0/1 背包 | O(n·cap) | O(cap) | AI017 300×30001 ≈ 9×10⁶；P3415 n×2881 |
| 二维费用背包 | O(n·W·C) | O(W·C) | AI025 80×151×151 ≈ 1.8×10⁶ |
| 枚举所有子集 | O(2ⁿ) | — | n = 30 约 10⁹，超时 |
10 / 渐进练习与参考答案
跟做 → 改一个条件 → 独立实现 → 迁移
每题先在纸上或文件里做完，再展开答案。
练习 1（跟做）：按第 05 节表的格式，把 AI017 题面示例 2（预算 5，(0,7)(6,9)(5,4)）逐件填出。
展开练习 1 答案
(0,7)：全部加 7 → 7 7 7 7 7 7；(6,9)：6 > 5，跳过；(5,4)：dp[5] = max(7, dp[0] + 4 = 11) = 11 → 7 7 7 7 7 11。答案 11。
练习 2（改一个条件）：每个模型可以部署任意多份（完全背包），预算 10、(3,7)(4,5) 的答案是多少？代码改哪里？
展开练习 2 答案
21：三份 (3,7)，显存 9。只把内层改成正序 for c in range(w, cap + 1)——正序读到的 dp[c-w] 已经含本物品，正是「可以重复选」的语义。0/1 版答案 12。
练习 3（改一个条件）：容量 5、两件 (2,3)(4,5)，「不超过」与「恰好装满」两种问法的最大价值各是多少？初始化怎么写？
展开练习 3 答案
不超过：5（选 (4,5)）。恰好装满：无解——2、4、6 都不是 5；初始化 dp[0] = 0、其余负无穷，转移只从可达格子出发，最后 dp[5] 仍是负无穷就报无解。全 0 初始化会把 dp[5] 算成 5，是错的。
练习 4（独立实现）：完成「代码自测」的 knap，再加三条断言：题面示例 1 → 13、示例 2 → 11、预算 0 且 (0,5)(0,3)(2,9) → 8。
展开练习 4 答案
knap 的参考实现（自带断言）
Pythondef knap(cap, items):
dp = [0] * (cap + 1) # dp[c] = 容量不超过 c 的最大价值
for w, v in items:
if w == 0: # 不占容量：对每个 c 都加上
dp = [x + v for x in dp]
continue
for c in range(cap, w - 1, -1): # 容量倒序：dp[c - w] 仍是没放本物品的旧值
dp[c] = max(dp[c], dp[c - w] + v)
return dp[cap]
# 单物品反例：这是检验倒序是否写对的最小用例
assert knap(4, [(2, 3)]) == 3 # 正序会得到 6
assert knap(5, [(2, 3), (3, 4), (4, 5)]) == 7 # 第 04 节逐件表
assert knap(10, [(3, 4), (4, 5), (5, 6), (2, 3)]) == 13 # AI017 题面示例 1
assert knap(5, [(0, 7), (6, 9), (5, 4)]) == 11 # AI017 题面示例 2：w = 0 直接部署
assert knap(0, [(0, 5), (0, 3), (2, 9)]) == 8 # 预算 0 也能部署不占显存的模型第一条断言输出 6 就是方向写反了。
练习 5（迁移）：把 knap 改成计数版 count_exact(people, cap)，用 P3409 的两组示例和 [5,5] / 3 → 0 验证。转移、初始化各改了哪一处？
展开练习 5 答案
count_exact 的参考实现（自带断言）
Pythondef count_exact(people, cap):
dp = [0] * (cap + 1) # dp[c] = 恰好坐 c 人的方案数
dp[0] = 1 # 一个团都不上：恰好 0 人，算 1 种
for p in people:
for c in range(cap, p - 1, -1): # 倒序：每个团至多上一次
dp[c] += dp[c - p] # 不选 + 选
return dp[cap]
assert count_exact([5, 4, 2, 3, 2, 4, 9], 10) == 4 # P3409 题面示例 1
assert count_exact([1, 2, 3, 4], 3) == 2 # 题面示例 2：[1,2] 或 [3]
assert count_exact([5, 5], 3) == 0 # 无解输出 0
assert count_exact([1, 2, 3, 4], 10) == 1 # 全部上车两处：max 换成 +=，全 0 换成 dp[0] = 1。倒序不变——每个团至多上一次。
11 / 读题要求与复习自评
四道题的要求对照，以及完成本课之后怎么复习
提交前把下表过一遍；题目页的题面与样例是最终依据。
| 项目 | AI017 | P3415 | P3409 | AI025 |
|---|---|---|---|---|
| 输入 | n C；n 行 w v | n；n 个字节数 | 逗号分隔人数；容量 | n W C；n 行 w c v |
| 容量 | C ≤ 30000 | 2880 块 | 汽车容量 < 100 | W、C ≤ 150 |
| 重量 / 价值 | w / v | ceil(size/512) / size | 人数 / 计数 | (w, c) / v |
| 初始化 | 全 0 | 全 0 | dp[0] = 1 | 全 0 |
| 输出 | 最大收益 | 最大总字节数 | 恰好坐满的方案数 | 最大收益 |
| 示例 | 4 10 … → 13 | 本课自算 | 5,4,2,3,2,4,9 / 10 → 4 | 3 10 10 … → 100 |
需要对照解法时，展开本课第 08 节的完整参考程序；题目页另有思路与参考代码，可在题目页查看。完成条件：本课算完成 = AI017、P3415 两道必做题都通过判题，并勾选全部六条「学习完成检查」；六条检查是自评，勾选不改变题目的通过（AC）状态；进阶练习与复习题单独统计，不影响完成状态。复习时用三个问题自测：① 不看正文，用单物品 (2,3)、容量 4 说明正序为什么得 6；② 不看表格，重算示例 1 的最后一行；③ 说出计数版与最值版在初始化和转移上的两处不同。答不出哪一条，就回到对应的节重读，再做第 10 节对应的练习。
12 / 练习
按顺序完成本课的任务
必做题已通过 0/2 道；进阶练习已通过 0/2 道
用单物品反例验证倒序（knap）
代码自测自主练习练习重点：0/1 背包基本写法 + 最小反例自测；预计用时：12 分钟
完成标准：能解释正序为什么等价于物品可重复选取
需要时查看提示
两个断言：第一个专门检查正序错误（输出 6 就是方向写反了），第二个对照正文的逐件表。参考实现在第 10 节练习 4 的展开区。
自测代码（复制到你的代码文件中运行，检查输出是否一致）
def knap(cap, items):
# 你来写：0/1 背包，容量倒序
...
# 单物品反例：这是检验倒序是否写对的最小用例
assert knap(4, [(2, 3)]) == 3 # 倒序：只能选一次
# 若实现输出 6，说明容量写成了正序，物品被选了两次
assert knap(5, [(2, 3), (3, 4), (4, 5)]) == 7 # 选 (2,3)+(3,4)AI017 · 显存装箱
必做任务 1练习重点：标准 0/1 背包 + w=0 模型的单独处理；预计用时：30 分钟
完成标准：能说出容量倒序的原因，以及 w=0 为什么可以直接计入
需要时查看提示
w_i = 0 且 v_i > 0 的模型无条件部署（对所有容量加收益）；v_i = 0 的直接跳过。C ≤ 30000，Python 双层循环上限 9×10⁶ 次，内层不要做多余的函数调用。第 05 节有示例 1 的逐件表。
P3415 · 通过软盘拷贝文件
必做任务 2练习重点：字节到块的单位换算 + 价值与重量分离；预计用时：25 分钟
完成标准：能说出重量为什么是块数、价值为什么仍是字节数
需要时查看提示
先读文件数 n，再读 n 个字节数。容量 2880 块；每个文件重量 (size + 511) // 512、价值 size。目标是「软盘中文件总大小最大」，即字节数而不是块数。第 06 节有自算用例。
AI025 · 双资源模型部署
进阶练习 1进阶练习练习重点：二维费用背包，两个容量维度都倒序；预计用时：30 分钟
完成标准：能解释只倒序一维时哪些用例会错、错在哪个方向
需要时查看提示
dp 开 (W+1)×(C+1)；任一维超预算的物品直接跳过；w=c=0 的正收益模型直接计入。两层容量循环都用倒序区间（range）：range(X, x-1, -1)。第 09 节有只倒序一维的错误输出。
P3409 · 代表团坐车
进阶练习 2进阶练习练习重点：恰好装满的方案数：取最大值换成加法、dp[0]=1；预计用时：20 分钟
完成标准：能说出计数版与求最值版在初始化和转移上的两处不同
需要时查看提示
第一行逗号分隔、第二行容量。dp[c] += dp[c-w]，容量仍然倒序（每个团至多上一次车）。dp[0] = 1 表示「什么都不选」这一种方案，是所有方案计数的起点；遗漏它，全表都会是 0。第 07 节有逐团表。
提交结果
提交结果说明与处理方法
- WA
答案错误
四查：容量方向（单物品反例）、w=0 的处理、单位换算（块与字节）、「恰好装满」的初始化。第 09 节的表给出了每种错误的具体输出。
- RE
运行错误
倒序区间 range(cap, w-1, -1) 里容量上限（cap）对应的下界写错会漏转移或越界；w > cap 的物品应被 range 自然跳过；P3409 第一行按逗号拆。
- TLE
超时
AI017 上限 9×10⁶ 次循环，Python 内层只做数组读写和比较，不调用多余的函数；仍超时就检查是否重复创建列表。
- AC
通过
用单物品边界用例验证同一物品不会被重复选取；再核对：双资源两个维度都倒序、计数版 dp[0]=1。
13 / 学习完成检查
本课学习完成检查
完成本课需要：必做题全部通过，并勾选本课的全部学习完成检查；进阶练习、基础加练与复习题单独统计，不影响完成状态。登录后，勾选记录会保存到账号，并更新课程总览的完成状态。