# 第 24 章 动态规划与背包问题体系


> 12 道真题编程题里有 3 道是背包问题，它也是六场笔试中唯一反复出现的算法模板。本章沿"状态定义 → 转移 → 初始化 → 遍历顺序 → 答案位置"这条流水线，把每个"为什么要这样写"讲透。

## 学习目标

读完本章，你应当能够：

1. 按五步流水线（状态定义、转移、初始化、遍历顺序、答案位置）独立完成一次动态规划（dynamic programming，DP）建模；
2. 用反例检验最优子结构与无后效性是否成立，并在不成立时扩充状态；
3. 说清 0/1 背包一维滚动必须倒序、完全背包（unbounded knapsack）必须正序的机理（读到旧值还是新值）；
4. 写出二维费用背包（两维都倒序）与分组背包（每层新开数组）的标准实现；
5. 辨析状态口径"恰好"与"不超过"的语义差别，并据此判断多输出题该选哪一种；
6. 完成方案还原的三类做法，并用"最小值/次小值"消掉附加约束转移中的一重枚举。

### 前置知识检查

| 你需要知道 | 在哪一节补齐 |
|---|---|
| 递归与"子问题"的概念 | 24.1 节从"重复计算"讲起 |
| 数组下标范围与循环边界 | 24.2 节统一约定容量维的遍历方向 |
| 复杂度估算与规模反推 | 第 22.2、22.3 节 |
| Python 列表推导与 `float('inf')` 的用法 | 24.3 节与第 26.5 节 |
| 浮点比较需要容差 | 第 26.2、26.3 节 |

## 24.1 DP 的成立条件：无后效性是状态定义的函数

一个递推式要叫动态规划，必须同时满足三条，缺一条写出来的东西就是错的：

| 条件 | 含义 | 检验方法 |
|---|---|---|
| **最优子结构**（optimal substructure） | 大问题的最优解由子问题的最优解组合而成 | 问"若子问题不是最优，大问题能更优吗"；若能，则子问题必须取最优 |
| **无后效性**（no aftereffect） | 状态一旦确定，后续决策只依赖状态本身，不依赖"怎么到达的" | 问"两条不同的到达路径，会不会对后续产生不同限制"；若会，状态定义不完备 |
| **重叠子问题**（overlapping subproblems） | 不同的大问题反复调用同一批子问题 | 若子问题互不重叠，那是分治而不是 DP |

【2026-08-05 编程题 2】要求不能连续两次调用同一个 Agent。若状态只记进度 `j`，即 `f[j] = 达到进度 j 的最小代价`，它就无法表达"上一次调用的是谁"。考虑两条都到达进度 `j` 的路径：

```
路径 A：… → Agent 1（代价 5）     进度 j
路径 B：… → Agent 2（代价 5）     进度 j
```

若下一步要调用 Agent 1，路径 A 被禁止（连续两次），路径 B 允许。**同一个状态 `j` 对后续决策的可用性不同** ⟹ 无后效性被破坏 ⟹ 状态定义不完备。修正方式是把"上一次调用的 Agent"并入状态得到 `f[j][k]`：这就是"扩充状态以恢复无后效性"。

> [!IMPORTANT]
> **无后效性不是问题的性质，而是状态定义的函数。** 同一个问题，状态写得好就有无后效性，写得差就没有。当转移写不下去时，第一反应应当是"我漏掉了什么信息"，而不是"这题不能用 DP"。

## 24.2 五步流水线

### 24.2.1 流水线的五步

```
① 状态定义：f[...] 的语义是什么？（一句话说清，且要含"恰好/不超过"的口径）
② 转移方程：f[当前] 由哪些 f[子] 推来？每项的物理含义是什么？
③ 初始化：最小的子问题取什么值？（决定边界是否正确）
④ 遍历顺序：按什么顺序填表？（决定每个 f[子] 读到的是旧值还是新值）
⑤ 答案位置：最终答案是哪个 f 值？（多输出题往往要事后扫描还原）
```
最容易出错的是 ① 和 ④：① 的口径写错会让整题的多输出失效，④ 的方向写错会让 0/1 背包退化成完全背包。

### 24.2.2 以 0/1 背包走一遍

`n` 件物品，第 `i` 件重 `w_i`、价值 `v_i`，容量 `C`，每件至多选一次，求最大总价值。

```
二维版本：
① f[i][c] = 只考虑前 i 件、容量不超过 c 时的最大价值
② f[i][c] = max( f[i−1][c], f[i−1][c − w_i] + v_i )   仅当 c ≥ w_i
③ f[0][c] = 0；f[i][0] = 0
④ i 从小到大；c 方向任意（读的是上一层 i−1，与 c 无关）
⑤ f[n][C]

一维滚动版本（省掉 i 那一维）：f[c] = max(f[c], f[c − w_i] + v_i)，仅当 c ≥ w_i
④ c 必须从大到小（倒序）遍历
```

```
为什么必须倒序——本章第一个必须讲透的机理：
设 C = 5，物品 w = 2、v = 10，f 初值全 0。
【正序 c = 0,1,2,3,4,5】
  c=2：f[2] = max(f[2], f[0]+10) = 10
  c=4：f[4] = max(f[4], f[2]+10) = 20    ← f[2] 已被本轮更新过
  ⟹ f[5] = 20 ⟹ 同一件物品被选了两次 ⟹ 这其实是完全背包的语义
【倒序 c = 5,4,3,2,1,0】
  c=4：f[4] = max(f[4], f[2]+10)，此刻 f[2] 还是旧值 0 ⟹ f[4] = 10
  c=2：f[2] = max(f[2], f[0]+10) = 10
  ⟹ f[5] = 10 ⟹ 每件物品至多用一次 ⟹ 正确的 0/1 语义
```

> [!IMPORTANT]
> 一维滚动时，若 `f[c − w]` 在同一轮里已被更新过，读到的是"选了当前物品之后"的新值，等价于允许重复选（完全背包）；若还没被更新，读到的是"没考虑当前物品"的旧值，等价于至多选一次（0/1 背包）。**倒序**时 `c − w < c`，小下标尚未更新，读到旧值，故是 0/1；**正序**时小下标已经更新，读到新值，故是完全背包。
>
> 判据可推广到所有背包变体：判断"某维该正序还是倒序"，只需问"我读的那个位置在同一轮里会不会被我提前改掉，我希望它是什么语义"。

初始化直接决定状态口径，三行代码的差别就是三种语义：

| 初始化 | 状态口径 | 含义 | 适用 |
|---|---|---|---|
| `f` 全 0 | **不超过** | 什么都不选是合法方案，价值 0 | 求最大值且空方案合法 |
| `f[0] = 0`，其余 `INF` | **恰好**（求最小） | 只有"恰好消耗 0"是可达起点 | 需要还原"实际消耗了多少" |
| `f[0] = 0`，其余 `−INF` | **恰好**（求最大） | 同上，用于求最大 | 需要精确匹配容量 |

这个区别在单输出题里往往看不出效果，在多输出题里是生死线（见 24.6.2 与 24.7）。

## 24.3 0/1 背包模板

```python
def knapsack01(weights, values, cap):
    # f[c] 口径是"容量不超过 c"，初值全 0 天然合法（什么都不选也是合法方案）
    f = [0] * (cap + 1)
    for w, v in zip(weights, values):
        # 倒序：保证 f[c-w] 读到的还是"没考虑当前物品"的旧值，即每件至多选一次
        for c in range(cap, w - 1, -1):
            f[c] = max(f[c], f[c - w] + v)
    return f[cap]
```

时间 `O(nC)`，空间 `O(C)`。求最小代价把 `max` 改 `min`、初值改 `INF`（恰好口径）；求方案数把 `max` 改 `+`、取 `f[0] = 1`；求"是否存在"用布尔数组并把 `f[0] = True`；物品有两个属性则升级为二维费用背包（24.5），物品分组则升级为分组背包（24.6）。

> [!WARNING]
> **求最小值的 0/1 背包必须用"恰好"口径。** 若照抄"不超过"的初值全 0，`f[c] = 0` 对一切 `c` 都表示"什么都不选"，`min` 会一路取 0，答案恒为 0。正确写法是 `f[0] = 0`、其余 `INF`，并在转移时跳过 `INF`（否则 `INF + v` 会污染最小值）。

## 24.4 完全背包

每件物品可选任意多次，求容量不超过 `C` 时的最大价值，解法是一维滚动 + **正序**遍历容量（机理见 24.2.2 的正序推演）。

```python
def knapsack_complete(weights, values, cap):
    # 完全背包：每件可选任意多次；f[c] 是"容量不超过 c"的最大价值
    f = [0] * (cap + 1)
    for w, v in zip(weights, values):
        # 正序：f[c-w] 在本轮已被更新为"考虑过当前物品"的值，
        # 于是同一物品可以继续叠加，恰好对应"可重复选取"
        for c in range(w, cap + 1):
            f[c] = max(f[c], f[c - w] + v)
    return f[cap]
```

### 24.4.1 完全背包加附加约束：状态往往不止一层

【2026-08-05 编程题 2】：`N` 个 Agent，第 `i` 个每调用一次推进 `p_i` 个百分点、花费 `c_i`，同一 Agent 可反复调用但**不能连续两次调用同一个**，进度达到或超过 100 即完成，求最小总代价。

```
① 状态：进度"达到或超过 100"即完成，真正有用的进度只有 0..99；
        又因"不能连续两次同一 Agent"，必须记住上一次是谁：
          f[j]    = 进度恰为 j 时的最小总代价
          last[j] = 取到 f[j] 时最后调用的 Agent
          s[j]    = 排除 last[j] 后、进度为 j 的最小总代价（次小值）
② 转移：j → j + p_k 时，base = s[j] if k == last[j] else f[j]
③ 初始化：f[0] = s[0] = 0，last[0] = −1；把起点写成"对每个 k 都取 min"，第一次调用不受限这条特例就并进了通用转移
④ 遍历顺序：p_i ≥ 1 保证进度严格递增，按 j 从小到大单向递推即可
⑤ 答案：所有 t = j + p_k ≥ 100 的候选中的最小值
```

**为什么不需要最短路**：`p_i ≥ 1` 意味着每次调用都让进度至少增加 1，所以转移总是从较小的 `j` 指向较大的 `j`，**状态图是有向无环图（directed acyclic graph，DAG）**，进度轴 `0 → 1 → 2 → … → 99` 上所有转移都从左指向右、不存在回边，按 `j` 升序单向递推就是正确的拓扑序。若 `p_i` 允许为 0，进度可能原地不动，图上出现自环，单向递推不再正确，必须用最短路（Dijkstra 或 Bellman-Ford 类）反复松弛。

> [!NOTE]
> 这条"上界 + 单向递推"的推理在机考中出现频率很高：**只要每一步都让某个单调量严格变化，状态空间就是 DAG，按该量的顺序递推即可**，不必担心"还需不需要再松弛一遍"。

### 24.4.2 消掉一重枚举：最小值与次小值

朴素做法让状态记全 `(进度 j, 上一个 Agent k)` 并枚举 `k` 与 `k'`，复杂度 `O(100·N²)`；`N = 10⁵` 时是 `10¹²` 量级，必然超时。突破口是：转移里对"上一个 Agent"的那重枚举**只求一个最小值**，可以预先算好。设第 `j` 层最小值为 `f[j]`、持有者为 `last[j]`，`s[j]` 为"排除 `last[j]` 之后该层的最小值"，则对任意 `k`：`k == last[j]` 时"排除 `k` 后的最小值"是 `s[j]`，否则是 `f[j]`。论证分两种情形穷尽：

```
情形 1：k == last[j]
  被排除的正是最小值的持有者
  ⟹ 剩下的候选恰好是"除 last[j] 之外的全部"
  ⟹ 它们的最小值按 s[j] 的定义就是 s[j]

情形 2：k != last[j]
  f[j] 的持有者不是 k，所以 f[j] 没有被排除
  ⟹ 它是"排除 k 之后"这个候选集合的成员
  ⟹ 而该集合是原集合的子集，其最小值不可能小于全层最小值 f[j]
  ⟹ 同时 f[j] 在集合内 ⟹ "排除 k 之后的最小值" = f[j]
  两情形穷尽，命题成立。∎
```

情形 2 的核心是**两边夹**：`min(子集) ≥ min(全集)`（子集性质）且 `min(子集) ≤ f[j]`（`f[j]` 在子集内），故相等。维护 `f`、`s`、`last` 的四条更新规则（把新候选 `cost`、Agent `k` 并入第 `t` 层）：

| 序号 | 条件 | 操作 | 理由 |
|---|---|---|---|
| 1 | `cost < f[t]` 且 `last[t] == k` | 只改 `f[t] = cost`，**不动 `s[t]`** | 同一 Agent 自己变便宜，次小值的持有者没变 |
| 2 | `cost < f[t]` 且 `last[t] != k` | `s[t] = f[t]`，再 `f[t] = cost`、`last[t] = k` | 老的最小值让位，其持有者与 `k` 不同，正合 `s[t]` 定义 |
| 3 | `last[t] != k` 且 `cost < s[t]` | 只改 `s[t] = cost` | 够不上最小值但能刷新次小值 |
| 4 | `last[t] == k` 且 `cost ≥ f[t]` | **直接丢弃** | 该候选与当前最小值同属一个 Agent，按定义不能进 `s[t]` |

**规则 1 是本题最容易写错的地方**：若把"变便宜的新候选"顺手写进 `s[t]`，`s[t]` 的持有者就与 `f[t]` 相同了，违反 `s[t]` 的定义，后续转移会取出错误的值。

```python
INF = float('inf')

def min_total_cost(n, p, c):
    """完全背包 + 相邻不同约束：f/s/last 三层信息把 O(100·N²) 降到 O(100·N)"""
    f, s, last = [INF] * 100, [INF] * 100, [-1] * 100
    f[0], s[0], ans = 0, 0, INF   # 虚拟起点：第一次调用不受"相邻不同"限制
    for j in range(100):      # p_i >= 1 ⟹ 进度严格递增 ⟹ 升序即拓扑序
        if f[j] == INF: continue
        for k in range(n):
            base = s[j] if k == last[j] else f[j]   # 撞上持有者就退而用次小值
            if base == INF: continue
            cost, t = base + c[k], j + p[k]
            if t >= 100:                           # 到达目标即结束，不入表
                ans = min(ans, cost); continue
            if cost < f[t]:
                if last[t] == k: f[t] = cost                    # 规则 1：同一 Agent 变便宜，s[t] 不动
                else: s[t], f[t], last[t] = f[t], cost, k        # 规则 2：老的最小让位成次小
            elif last[t] != k and cost < s[t]: s[t] = cost       # 规则 3：刷新次小值
            # 规则 4：last[t] == k 且未便宜过 ⟹ 落在两个分支之外，丢弃
    return -1 if ans == INF else ans
```

**无解判定**只有一种情形：`N == 1` 且 `p_1 < 100`。`N = 1` 时第二次调用必然撞上同一个 Agent，只能调用一次，进度封顶在 `p_1`；`N ≥ 2` 时两个 Agent 交替（`1, 2, 1, 2, …`），每次调用让进度至少涨 1 且没有上界，必然越过 100。

> [!WARNING]
> 无解判定必须写成这条精确条件，**不能用"`ans == INF`"这类运行结果去反推**——那样在 `N ≥ 2` 但输入特殊时可能误判。同时注意 `N = 1, p_1 ≥ 100` 时"只调用一次"是合法的，答案就是 `c_1`。

## 24.5 二维费用背包

每件物品消耗两种资源，背包对两种资源各有上限，每件至多选一次。状态 `f[a][b] = 资源一不超过 a、资源二不超过 b 时的最大收益`，转移 `f[a][b] = max(f[a][b], f[a − x][b − y] + w)`（当 `a ≥ x` 且 `b ≥ y`）。实现上的全部要点就是**两维都倒序**：

```
for x, y, w in tasks:
    for a in range(cap_a, x - 1, -1):        # 两维都倒序
        for b in range(cap_b, y - 1, -1):
            f[a][b] = max(f[a][b], f[a - x][b - y] + w)
```

与一维同理，任一维正序，都会让该维上"已被当前物品更新过的位置"被再次读取，从而允许同一物品被选两次。

### 24.5.1 收益并列时还原最小资源用量

【2026-08-26 编程题 1】要求在最大收益前提下输出实际的内存与算力消耗，收益并列时优先内存更小，内存也相同则算力更小。解法是利用"不超过"口径下 `f` 沿两维**单调不减**这一性质做**两边夹**还原：设 `best = f[A][B]`，`a* = min{ a : f[a][B] == best }`，要证**存在收益为 `best` 的方案，其资源消耗恰好是 `(a*, b*)`**，其中 `b* = min{ b : f[a*][b] == best }`。

```
上界方向：f[a* − 1][B] < best
  a* 是"使 f[·][B] 达到 best 的最小下标" ⟹ a* − 1 未达到 best
  ⟹ 任何收益为 best 的可行方案，其内存消耗都不可能 ≤ a* − 1
  ⟹ 所有 best 方案的内存消耗都 ≥ a*      （整数性：≤ a*−1 不成立 ⟹ ≥ a*）
下界方向：f[a*][B] == best ⟹ 确实存在一个内存不超过 a* 的 best 方案
两侧合并：该方案的内存恰好等于 a*        （≥ a* 且 ≤ a*）∎
```

算力同理：**先锁定第 `a*` 行**，再沿 `b` 找第一个使 `f[a*][b] == best` 的 `b`。

```python
best, mem, cal = f[A][B], 0, 0
while f[mem][B] < best:      # 先沿 a 夹：第一个达到 best 的 a 就是真实内存
    mem += 1
while f[mem][cal] < best:    # 锁定该行后再沿 b 夹（不能同时对两维夹，见 24.7）
    cal += 1
```

> [!IMPORTANT]
> 这个"两边夹"成立有**两个前提**，缺一不可：一是 **`f` 沿两维单调不减**，它来自"不超过"口径与初值全 0，若状态写成"恰好"，`f[a][B]` 不再单调，第一个等于 `best` 的位置可能不是最小消耗；二是**资源消耗是整数**，所以"不 ≤ a*−1"可以推出"≥ a*"，若资源是浮点数，夹逼会漏掉 `(a*−1, a*)` 之间的值。
>
> 另外**不能直接把上限 `A`、`B` 当作答案**：样例 1 中 `A = 12`，而取到最优收益的方案只用掉了 10 和 9。

## 24.6 分组背包

`n` 组物品，每组若干件，**每组恰好选一件**（或至多选一件），在容量约束下最优化目标。与 0/1 背包的根本差别是：一个组内的物品**互斥**，不能同时选。

### 24.6.1 为什么不能原地滚动

0/1 背包用倒序滚动，是因为"每件物品至多选一次"；分组背包的约束更强：同一组内至多（或恰好）选一件。

```
若在容量轴上原地滚动处理同一组的物品：
  for item in group:
      for j in range(C, c_item - 1, -1):
          f[j] = min(f[j], f[j - c_item] + t_item)
  处理组内第 2 件时，f[·] 里已经混入了"选了第 1 件"的状态，
  于是可能得到"同一组选了两件"的方案 —— 违反约束。
正确做法：每层新开一个数组 g，从 f 转移，处理完整组后再 f = g：
  g[j + c] = min(g[j + c], f[j] + t)     对组内每个物品、每个可行 j
```

`g` 的每个位置只由 `f`（上一组结束时的状态）推出，**组内至多选一件**自然成立。

```python
INF = float('inf')

def group_knapsack_exact(cap, groups):
    """分组背包（每组恰好选一件），口径为"消耗恰好为 j"。
    groups[g] = [(cost, time), ...]，返回 (最小总耗时, 达到该耗时的最小消耗)。"""
    f = [INF] * (cap + 1)
    f[0] = 0                                  # 恰好口径：只有消耗 0 可达
    for group in groups:
        g = [INF] * (cap + 1)                 # 每层新开数组：原地滚动会让同组选到两件
        for j in range(cap + 1):
            if f[j] == INF: continue
            for cost, time in group:
                if j + cost <= cap and f[j] + time < g[j + cost]:
                    g[j + cost] = f[j] + time  # 源是 f（上一组），不是 g
        f = g
    # 升序扫描 + 严格小于：第一次取到最小耗时的 j 就是最省资源的方案
    best_time, best_cost = INF, 0
    for j in range(cap + 1):
        if f[j] < best_time:
            best_time, best_cost = f[j], j
    return best_time, best_cost
```

### 24.6.2 "恰好"口径与升序扫描

【2026-09-04 编程题 2】要求输出最小总耗时、实际总资源消耗、剩余资源量三个量，且"总耗时并列时取实际消耗最小"。这就是必须用"恰好"口径的原因：

```
若 f[j] = 消耗不超过 j 时的最小耗时：
  f[j] 对所有 j ≥ 最优消耗 都等于同一个最小值（"不超过"是宽松的）
  ⟹ 消耗信息被抹掉 ⟹ 无法回答"实际消耗是多少"
若 f[j] = 消耗恰好为 j 时的最小耗时：
  每个 j 对应一个确切的消耗量 ⟹ 扫一遍就能在并列的最小耗时里挑出消耗最小的
```

初始化 `f[0] = 0`、其余 `INF`；`INF` 表示"这个消耗量不可达"，正是"恰好"口径的体现。还原时从 `j = 0` 升序扫描、`f[j] < best_time` 才更新：升序保证先遇到的 `j` 消耗更小，严格小于保证相等时保留先遇到的那个，**两者合起来等价于"耗时并列取消耗最小"，第一次取到最小耗时的 `j` 必是达到该耗时的最省资源方案**。

> [!WARNING]
> 若把严格小于写成 `≤`，**最后一个**达到最小耗时的 `j` 会成为答案，恰好取到最大消耗——与题目要求完全相反。**这一处符号是分组背包题的第一号失分点。**
>
> 样例 1 实测：`2 15 / 5 6 8 3 / 7 5 9 2`，最小耗时 8 有两套方案，消耗分别为 15 和 14，答案应输出 14。

三种背包的最终对照：

| 维度 | 0/1 背包 | 完全背包 | 分组背包 |
|---|---|---|---|
| 选取限制 | 每件至多一次 | 每件任意次 | 每组恰好/至多一件 |
| 一维滚动方向 | 容量维**倒序** | 容量维**正序** | **每层新开数组**（不可原地滚动） |
| 状态口径 | 常为"不超过" | 常为"不超过" | 多输出题常用"恰好" |
| 典型复杂度 | `O(nC)` | `O(nC)` | `O(nC)`（组内物品贡献常数倍） |
| 本书真题 | 二维费用版：08-26 编程题 1 | 08-05 编程题 2 | 09-04 编程题 2 |

## 24.7 方案还原的三类做法

12 道真题里有 8 道要求输出多个量，几乎都需要"还原"：从 DP 表反推达成最优解的具体选择。**记录前驱**在转移成功时记下这一步从哪里来，最后从答案位置倒推，空间从 `O(C)` 升到 `O(nC)`，换来的是能回答"具体选了哪些物品"；**前缀最值夹逼**不记录任何前驱，靠 DP 表本身的单调性事后扫描，即 24.5.1 的做法；**升序扫描 + 严格小于**即 24.6.2 的做法，一次扫描同时给出最优值与最省资源的那套方案。

| 做法 | 额外空间 | 适用问题 | 本书真题 |
|---|---|---|---|
| 记录前驱 | `O(状态数)` | 需要输出"选了哪些物品" | 一般背包还原题 |
| 前缀最值夹逼 | `O(1)` | 输出"最小资源用量" | 08-26 编程题 1 |
| 升序扫描 + 严格小于 | `O(1)` | 输出"最省资源的那套方案" | 09-04 编程题 2 |

资源有多个维度时，夹逼必须**逐维锁定**，不能同时对两维夹：先在完整二维表上沿第一维夹出 `a*`，固定 `a*` 后在 `f[a*][·]` 这一行上沿第二维夹出 `b*`，再固定 `(a*, b*)` 沿第三维继续。**为什么不能同时对两维夹**：若同时对 `a`、`b` 取最小，可能得到一个"两维都不超过 a*、b*"的位置，但那里并不存在任何一个真实方案恰好用掉 `(a*, b*)`；逐维锁定的作用就是**每一步都在"确实存在最优方案"的约束下前进**。

## 24.8 上界与剪枝

DP 的规模由"状态数 × 每个状态的转移数"决定。规模逼近安全线时，可从三个方向压缩：**压缩状态**（去掉无用状态，如进度只到 99、超过即出答案）；**压缩转移**（用前缀最值或单调队列把"枚举全部前驱"变成 `O(1)`，收益一整个量级，需要单调性论证）；**压缩空间**（滚动数组或只保留相邻层，代价是无法还原具体方案）。

**上界剪枝**指利用目标的上界提前终止或跳过状态，机考中常见的三种形态：一是**容量上界裁剪**，`j + c > C` 的转移直接跳过（所有背包题都在用）；二是**答案上界提前定界**，若当前代价已不小于已找到的答案就跳过该状态；三是**目标到达即出**，如 24.4.2 代码里的 `if t >= 100: ans = min(ans, cost); continue`——到达目标后不再展开它的后继。

> [!TIP]
> 第三种剪枝值得单独记住：**当"到达目标的动作"本身就意味着结束，目标之后的状态全部不需要**。这把一个可能无界的状态空间截成了一个只有 100 个点的有限表。看到"达到或超过某阈值即结束"这类描述时，第一反应就该是"把状态空间截断在这里"。

再强调 24.4.1 的结论：**当每一步都使某个量严格单调变化时，状态图是 DAG，按该量的顺序单向递推即可**。标准完全背包里这个量是容量 `c`（每次装入使容量消耗增加 `w ≥ 1`），08-05 编程题 2 里是进度 `j`（每次调用使进度增加 `p_i ≥ 1`）。反例是 `p_i = 0`：状态图上出现自环，单向递推不再保证最优，必须用最短路算法反复松弛。**这就是"不需要最短路"这一结论的边界。**

## 本章小结

| 关键结论 | 一句话表述 | 常见错误 |
|---|---|---|
| DP 的成立条件 | 最优子结构 + 无后效性 + 重叠子问题，缺一不可 | 把无后效性当成问题的固有性质，而不是状态定义的函数 |
| 状态定义优先 | 转移写不下去时先问"我漏了什么信息" | 强行用不完备的状态，答案随枚举顺序漂移 |
| 0/1 背包倒序 | 倒序保证 `f[c−w]` 读到旧值（没考虑当前物品） | 写成正序，退化成完全背包 |
| 完全背包正序 | 正序让 `f[c−w]` 读到本轮已更新的新值 | 写成倒序，每件物品只能用一次 |
| 二维费用 | **两维都倒序**，任一维正序都会允许重复选 | 只把第一维倒序，第二维忘了 |
| 分组背包 | 每层**新开数组**，原地滚动会让同组选到两件 | 照搬 0/1 背包的滚动写法 |
| 状态口径 | "不超过"（初值全 0）与"恰好"（`f[0]=0` 其余 `INF`）语义不同 | 多输出题用"不超过"，消耗信息被抹掉 |
| 求最小值 | 必须用"恰好"口径，否则 `min` 一路取 0 | 求最小值却用初值全 0 |
| 单调不减 | "不超过"口径下 `f` 沿容量维单调不减，是夹逼还原的前提 | 状态写"恰好"却用夹逼法还原 |
| 两边夹还原 | 上界来自"前一位达不到 best"，下界来自"这一位达到 best" | 直接把容量上限当成答案输出 |
| 逐维锁定 | 多维还原必须一维一维夹，不能同时夹两维 | 同时对两维取最小，得到不存在对应方案的位置 |
| 升序 + 严格小于 | 两条件合起来等价于"耗时并列取消耗最小" | 写成 `≤`，恰好取到最大消耗 |
| 最小值/次小值 | "排除任一元素后的最小值只能是全层最小值或次小值" | 忘了次小值的持有者必须与最小值不同（规则 1） |
| 单向递推与剪枝 | 单调量严格变化 ⟹ 状态图是 DAG ⟹ 升序递推；到达目标即不入表 | 单调量可能不变时仍用单向递推，或不截断导致状态无界 |

## 自测题

**Q1**（辨析）把 0/1 背包的容量循环从倒序改成正序会发生什么？给一个具体输入，算出两种顺序的不同结果。

<details><summary>答案与解析</summary>

正序会让**同一件物品被选多次**，即把 0/1 背包变成完全背包。算例：容量 `C = 4`，一件物品 `w = 2`、`v = 10`。

```
【正序】f 初值 [0,0,0,0,0]
  c=2：f[2] = max(0, f[0]+10) = 10
  c=4：f[4] = max(0, f[2]+10) = 20    ← 用了本轮刚更新的 f[2]，相当于选了 2 次
【倒序】
  c=4：f[4] = max(0, f[2]+10) = 10    ← f[2] 还是旧值 0，选了 1 次
  c=2：f[2] = max(0, f[0]+10) = 10
```

机理：`f[c − w]` 的下标严格小于 `c`，正序时小下标先被处理、读到的是"已考虑当前物品"的值。**通用问法是"我希望 `f[c−w]` 是旧值还是新值"**，它适用于一切"滚动数组 + 选取次数受限"的场景。

</details>

**Q2**（设计）给定 `n` 个任务，每个任务有方案 A（消耗 `a₁`、收益 `p₁`）与方案 B（消耗 `a₂`、收益 `p₂`），每个任务必须选一个方案，总消耗不超过 `C`，求最大总收益。写出状态定义与转移，并说明为什么不能原地滚动。

<details><summary>答案与解析</summary>

这是**分组背包（每组恰好选一件）**：

```
① 状态：f[j] = 前若干组处理完、总消耗恰好为 j 时的最大收益
   初值 f[0] = 0，其余 −INF（−INF 表示该消耗量不可达）
② 转移：g[j + a₁] = max(g[j + a₁], f[j] + p₁)   若 j + a₁ ≤ C
        g[j + a₂] = max(g[j + a₂], f[j] + p₂)   若 j + a₂ ≤ C
   处理完该组后 f = g
⑤ 答案：max{ f[j] : 0 ≤ j ≤ C }
```

**为什么不能原地滚动**：若直接在 `f` 上滚，处理方案 A 时 `f[j + a₁]` 被更新，随后处理方案 B 时可能读到"已经选了方案 A"的状态，得到"同一任务选了两个方案"的非法结果。用新数组 `g` 隔离后，`g` 的每个位置只由 `f`（上一组结束时的状态）推出，组内互不影响。若改成"每组至多选一件"，把 `g` 初始化为 `f` 的副本（`g = f[:]`）即可允许"一个都不选"，但转移的源仍必须是 `f[j]` 而不是 `g[j]`：源只能是"上一组的状态"。

</details>

**Q3**（推导）证明：在"不超过"口径的二维费用背包中，`f[a][b]` 沿 `a` 与沿 `b` 都单调不减。

<details><summary>答案与解析</summary>

`f[a][b]` 表示内存不超过 `a`、算力不超过 `b` 时的最大收益。设 `a₁ < a₂`，任取满足"内存 ≤ a₁、算力 ≤ b"的可行方案 `S`，它同时也满足"内存 ≤ a₂、算力 ≤ b"，所以

```
{S : 可行于 (a₁, b)} ⊆ {S : 可行于 (a₂, b)}
⟹ max 收益（前者） ≤ max 收益（后者）
⟹ f[a₁][b] ≤ f[a₂][b]                                    ∎
```

`b` 方向完全对称。这条性质有两个前提：**"不超过"口径**（可行集是"≤ a"这个下集，改成"恰好为 a"后可行集不再单调扩张，性质立刻失效）与**初值全 0**（空方案必须合法，才能保证可行集在任意 `(a, b)` 下非空）。它正是 24.5.1 两边夹的依据。若题目要求"必须恰好选若干个、不能什么都不选"，空方案不合法，应改用"恰好"口径并放弃夹逼还原，改为记录前驱。

</details>

**Q4**（论证）在 08-05 编程题 2 中，设第 `j` 层最小代价为 `f[j]`、持有者为 `last[j]`，次小代价为 `s[j]`。对某个非持有者 `k`（`k != last[j]`），为什么"排除 `k` 之后的最小值"等于 `f[j]`？说明"两边夹"的每一步。

<details><summary>答案与解析</summary>

设原候选集合 `U` 为所有"以进度 `j` 结束、最后一次调用某个 Agent"的 `(代价, Agent)` 二元组，排除 `k` 后为 `U_k = U \ {(·, k)}`。因 `k != last[j]`，持有最小值的元素 `(f[j], last[j])` 不属于被排除的部分，故 `(f[j], last[j]) ∈ U_k`。

```
下界方向：U_k ⊆ U ⟹ min(U_k) ≥ min(U) = f[j]
          （子集的最小值不可能小于全集的最小值）
上界方向：(f[j], last[j]) ∈ U_k ⟹ min(U_k) ≤ f[j]
          （集合中存在值为 f[j] 的元素，其最小值不超过它）
两侧合并：min(U_k) = f[j]                                  ∎
```

**为什么必须这样论证**：转移 `j → j + p_k` 时，若 `k` 恰好是"达到 `j` 的最小代价的最后一步"，那个最小代价方案被禁止使用（会连续调用同一 Agent），必须退而用次小值；否则可以直接用最小值。**易错点**：把 `f` 与 `s` 理解成"按代价排序取前两名"是对的，但维护时必须保证 `s[j]` 的持有者与 `last[j]` 不同（规则 1）；若在"同一 Agent 自己变便宜"时顺手把新值也写进 `s[j]`，命题前提被破坏，后续转移全部失效。

</details>

**Q5**（设计）【09-04 编程题 2】要求"总耗时并列时取实际消耗最小"。说明若状态口径写成"消耗不超过 j"，为什么第二个输出无法得到。

<details><summary>答案与解析</summary>

"不超过"口径下 `f[j]` 是"消耗 ≤ j 时的最小耗时"。一旦某个消耗量 `j₀` 能达到全局最小耗时 `T*`，对所有 `j ≥ j₀` 都有 `f[j] = T*`，因为"不超过 `j`"比"不超过 `j₀`"更宽松，可行集只增不减。于是整条 `f` 数组在 `j ≥ j₀` 的区间上是一段常数：

```
"不超过"：f = INF INF 8 8 8 8 8 8 …      ← j ≥ j₀ 全是 8，看不清真实消耗
"恰好"：  f = INF INF 8 10 8 12 9 …      ← j=2 与 j=4 都达到 8，但方案不同
                    ↑     ↑
              j₀ / j=2   j=4
```

所有 `j ≥ j₀` 都报告同一个值，而它们对应的真实方案可能消耗 `j₀`、也可能消耗 `j₀ + 3`，**信息已经不存在了**。改成"恰好"口径后每个 `j` 对应一个确切消耗量，再升序扫描、`f[j] < best_time` 才更新（严格小于保证并列时保留先遇到的、消耗更小的那个），第一次取到 `T*` 的 `j` 就是最省资源的方案，第三个输出 `C − best_cost`（剩余资源量）也随之确定。**一般规律：题目要求输出"实际用量"时，状态口径几乎一定是"恰好"。**

</details>

**Q6**（计算）完全背包：容量 `C = 10`，物品 `(w, v) = (3, 5)` 与 `(4, 7)`，每件可无限次取。用正序一维滚动求最大价值，并写出 `f` 数组的变化过程。

<details><summary>答案与解析</summary>

`f` 初值 `[0]*11`（下标 0..10），口径为"容量不超过 `c` 的最大价值"。

| 阶段 | `c` | 计算 | `f[c]` |
|---|---|---|---|
| (3,5) | 3 | `max(0, f[0]+5) = 5` | 5 |
| (3,5) | 6 | `max(5, f[3]+5) = 10` | 10 |
| (3,5) | 10 | `max(10, f[7]+5) = 15` | 15 |
| (4,7) | 8 | `max(10, f[4]+7) = 14` | 14 |
| (4,7) | 10 | `max(15, f[6]+7) = 17` | 17 |

最终 `f[10] = 17`。**验证**：`10 = 3 + 3 + 4`，价值 `5 + 5 + 7 = 17`。其中 `f[6] = 10` 是"两个 (3,5)"，说明正序确实让同一物品被取了两次——这正是完全背包需要的行为；若改成倒序，每件物品至多取一次，`f[10]` 只会是"各取一件"的 12。

</details>

## 与真题的关联

| 真题 | 考查角度 | 对应本章小节 |
|---|---|---|
| 【2026-08-05 编程题 2】多 Agent 协作任务调度 | 完全背包 + "相邻不同"约束；最小值/次小值消掉一重枚举；进度 ≥ 100 即出答案的上界剪枝 | 24.4.1、24.4.2、24.8 |
| 【2026-08-26 编程题 1】运维任务收益最大化 | 二维费用背包两维倒序；"不超过"口径下 `f` 单调不减；两边夹还原最小内存与最小算力 | 24.5、24.5.1、24.7 |
| 【2026-09-04 编程题 2】模型训练任务的资源分配 | 分组背包每组必选一件 ⟹ 每层新开数组；"恰好"口径；升序 + 严格小于取最省资源 | 24.6.1、24.6.2、24.7 |
| 【2026-09-09 编程题 1】动态 KV 缓存稀疏优化 | 名额分配型问题：把"反复取前 k 名"换成一次排序（贪心而非背包，但状态定义思想相通） | 24.2、24.8 |
| 【2026-09-04 编程题 1】时间序列清洗与特征评分 | 多阶段口径纪律（每一步用上一步结果还是原值），与"遍历顺序决定读到旧值还是新值"同源 | 24.2.2 |
| 【2026-09-11 编程题 1】端侧大模型动态权重剪枝 | 自定义比较器维护窗口最优，与"最小值/次小值"同为"用少量附加信息消掉重枚举" | 24.4.2 |

## 延伸阅读

- Cormen, Leiserson, Rivest, Stein，《Introduction to Algorithms》第 15 章——最优子结构与无后效性的标准定义，装配线调度与矩阵链乘两个完整案例。
- Bellman, R.《Dynamic Programming》（1957）——"最优性原理"的原始论述，理解无后效性的历史来源。
- 《背包问题九讲》（dd_engi）——背包问题的中文经典整理，可与之对照阅读本章在"为什么"层面的补充。
- Kleinberg & Tardos，《Algorithm Design》第 6 章——从"带权区间调度"到"最短路径"的建模过程，对"如何发现状态"讲得最细。


---

> 作者: [破戒僧](https://onlyblacktea.cn)  
> URL: https://onlyblacktea.cn/book/ai/ch24/  

