# 第 25 课实验 · 动态规划（0/1 背包 / 完全背包 / 恰好装满 / 分组背包）参考解

这个目录是 `lab/0025-dp-knapsack/` 的参考解：四个任务文件里每一段 TODO 都填好了，
`run_tests.py` 与 `tools.py` 和空模板那一份**逐字节相同**。在**这个目录里**直接跑：

    py run_tests.py

期望结果：四个任务全过，最后一行是 `四个任务全过。`，退出码 0
（本机现在是 176 PASS / 0 FAIL）。

空模板那一份（`lab/0025-dp-knapsack/`）跑同一个判分脚本时，四个任务文件各自
**也能跑出完整的打印**（不会崩、不会 Traceback），只是每一行都被判成 FAIL——
而且每一条 FAIL 都会点名是哪个 TODO 没写。这正是这一课要练的两条主线。

## 一、四个任务

| 任务 | 文件 | 要写的 TODO | 这一课练的是什么 |
| --- | --- | --- | --- |
| 1 | `task1_knap01.py` | TODO 1 `knap01_2d`、TODO 2 `knap01_1d_rev` | 0/1 背包的两种等价写法：二维表的 `dp[i][c]`，与压成一维后**内层逆序** |
| 2 | `task2_direction.py` | TODO 1 `knap01_1d_fwd`、TODO 2 `knap_complete`、TODO 3 `first_wrong` | 内层循环方向：正序把 0/1 背包写成了完全背包，答案只会**偏大**，要能揪出反例 |
| 3 | `task3_exact.py` | TODO 1 `knap01_exact`、TODO 2 `knap01_exact_rev`、TODO 3 `probe_exact`、TODO 4 `first_short` | 「恰好装满」与「不超过」只差初始化；负无穷怎么填、怎么比 |
| 4 | `task4_complete_group.py` | TODO 1 `knap_complete2`、TODO 2 `knap_complete_cap`、TODO 3 `knap_group` | 完全背包的两种写法，与分组背包的三层循环次序 |

## 二、为什么是这四个任务

**任务 1** 先把「同一件不会被拿第二次」这件事钉死在二维表上：拿的那一支查的是
`dp[i-1][c-w[i-1]]`（前 i-1 件），不是 `dp[i][…]`。看懂了这个下标，一维版为什么
必须逆序就不言自明了——逆序时 `dp[c-w[i]]` 还没被本轮改过，所以它一定还是
「前 i-1 件」的结果。

**任务 2** 把内层方向单独拎出来做对照实验：同一个初始化、同一批数据，只把内层
改成正序，答案就**总是偏大**，而且**恰好等于完全背包**。判分按种子 **5** 造
400 组 0/1 数据自己数：正序错 **297** 组、逆序错 **0** 组。课件里那个反例是
重量 `[6, 9, 1, 8, 4]`、价值 `[2, 6, 4, 12, 16]`、容量 `8` → 逆序 20、正序 32、
枚举 20。（种子与取数次序是判分接口，别改。）

**任务 3** 换问题而不是换写法：「恰好装满」只把 `dp[0]` 设 0、其余全设负无穷。
非法状态用负无穷（不是 0）是对这一问唯一的正确初始化——写成全 0 会让它悄悄
交回「不超过」那一问的答案：数看着正常、合法，但回答的不是你问的问题。
重量 3/5/7 时恰好凑不出的容量是 **1、2、4、6、9、11、13、14**。

**任务 4** 收在两种「可以重复拿」的写法上：完全背包的物品在外、容量正序，
与逐容量从小到大推那一版处处一致（300 组 0 组不一致）；分组背包是
**组在外、容量在中逆序、组内物品在最里**，容量那一层的逆序保证一组里最多拿一件。

## 三、最容易踩的坑

1. **一维 0/1 背包内层写成正序**——这是本课最贵的一个错：答案不会崩、
   不会报错，只是偏大，而且偏得跟完全背包一模一样。任务 1 的「对拍 两版处处一致」
   与任务 2 的 297/400 都在盯它。
2. **「恰好装满」用全 0 初始化**——交回的是「不超过」的答案。要看的是那些
   凑不出来的容量（1、2、4、6、9、11、13、14）是否还是负无穷。
3. **拿负无穷去比大小**：`float('-inf') <= 3` 是合法的，但 `-inf + 价值` 还是
   `-inf`，所以状态转移前要先判 `dp[c - w] != NEG`，否则「凑不出来」会被
   当成一个大负数一路搬下去。
4. **把负无穷写成 None 或 0**：这一课的 `tools.fmt` 认 `-inf` 与 `无解` 两种原样，
   但**值本身**必须是 `float('-inf')`。判分对「无解」这一类是**按值**认的。
5. **分组背包把物品那一层放到容量外面**——一组里就会拿好几件，答案偏大。
6. **改判分接口**：文件名、函数名、函数签名、`CASES_*` 的种子与上限、
   带 `# 别改` 的每一行打印，都是判分接口。判分自己按同一个种子复现同一批数据，
   你改了种子它就对不上，直接判 FAIL。

## 四、判分到底看什么

`run_tests.py` 每个任务都走**两条证据路**：

1. **读脚本自己打印的行**。四个任务文件各自的 `__main__` 会把参数、每一批随机
   数据的 JSON、每一条用例的答案都打出来。判分按**标签整段**认行
   （`<标签>` 后面跟空白或没有，绝不做前缀匹配），再拿判分**自己那份**参照实现
   （二维表 / 逆序一维 / 枚举 / 逐容量递推 / 分组枚举 / 恰好装满）重算期望值逐项对照。
   **答案对了才算过，不是「打印了就算过」。**
2. **另起一个探针进程** import 你的任务文件当模块 `m`，拿判分**自己单独种子的数据**
   去调你的函数：任务 1 试二维版与逆序一维版（判分造 15 组）；任务 2 试正序错版、
   完全背包与 `first_wrong`（12 组）；任务 3 试「恰好装满」「`probe_exact`」
   「正序那一版」与 `first_short`（12 组）；任务 4 试完全背包两版与分组背包
   （10 组 + 8 组）。探针数据全在判分手里，所以「判分用一套数据、脚本用另一套」
   这个坑不存在。

判分只判**确定值**：价值、偏大的数额、负无穷的格、对拍的组数、反例那一组、
无解的容量个数。**秒数一律不判**（本机实测、会浮动，只当趋势看）。

判分还会认一认「这一段是不是还没写」：它起一次探针，看那几个 TODO 函数是不是
清一色交回负无穷或 None。是的话，每一段相关的 FAIL 后面都会补一句
「这一条要 TODO n 写出来才可能过」——所以空模板跑出来**每一条 FAIL 都点得出是哪个 TODO**。

### 任务分节对照

| 任务 | 第二个证据路（探针）在验什么 | 可能出现的 FAIL 在说什么 |
| --- | --- | --- |
| 1 | 二维版与逆序版在判分自造的 15 组上逐组对枚举 | 「TODO 1 与 TODO 2 都要给出枚举出来那个数」 |
| 2 | 正序版与完全背包在 12 组上处处相等；`first_wrong` 交出 (容量, 枚举, 正序) | 「正序那一版只会偏大、不会偏小」 |
| 3 | 恰好装满、`probe_exact` 与正序版在 12 组上的值；`first_short` 交出 (容量, 恰好装满, 正序) | 「TODO 3 的 probe_exact 必须与 TODO 1 给出同一个值」 |
| 4 | 完全背包两版在 10 组、分组背包在 8 组上对枚举 | 「分组背包该与枚举每组取法的答案一样」 |

## 五、目录里有什么

| 文件 | 说明 |
| --- | --- |
| `tools.py` | 给好的工具：造数据、枚举参照实现、格式化打印。与空模板那份逐字节相同。 |
| `run_tests.py` | 判分脚本。与空模板那份逐字节相同。 |
| `task1_knap01.py` … `task4_complete_group.py` | 四个任务的**参考解**（TODO 都填好了）。 |
| `README.md` | 本文件。 |

跑法（在这个目录里）：

    py task1_knap01.py      # 单个任务，看它自己打印的那些行
    py run_tests.py         # 判分，四个任务一起判