动态规划 · HTML
数学 / 逻辑形态
dp[c] 表示容量/总和 c 的答案。0/1：对每个 (w,v)，c 从 C 降到 w 更新 dp[c]=Agg(dp[c],dp[c-w]⊕v)；完全背包则 c 递增。
识别信号
- 每个对象有重量/代价与可选价值。
- 目标围绕容量、总和、分割或硬币。
- 每项有选/不选，多个子集到达相同容量。
- 容量上界可接受 O(nC) pseudo-polynomial。
- 题目区分每项一次、无限次或有界次数。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 容量巨大但物品很少 | O(nC) 不可行；考虑 meet-in-the-middle、稀疏集合或值维 DP。 |
| 顺序本身有意义 | 组合背包按物品外层去重顺序；若排列顺序计数，循环结构不同。 |
| 贪心按价值密度 | 只对可分割物品成立；0/1 背包不能拆分，密度贪心不保证最优。 |
核心不变量
处理完前 i 种物品后，dp[c] 只包含按当前复用规则可由这些物品形成的答案；0/1 降序确保本轮物品不会被重复读取。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 容量/总和 c 的可行性、最优值或计数；不可达用 False/-inf/inf。 |
| Transition | 从不选的旧 dp[c] 与选当前物品后的 dp[c-w] 合并；循环方向决定 dp[c-w] 是上一物品层还是当前层。 |
| Frontier / order | 物品层从前到后；容量轴在 0/1 中逆向、完全背包中正向。 |
Python 骨架
def zero_one_max_value(items, capacity):
dp = [0] * (capacity + 1)
for weight, value in items:
for c in range(capacity, weight - 1, -1):
dp[c] = max(dp[c], dp[c - weight] + value)
return dp[capacity]
正确性思路
- 初始时不选任何物品，容量状态符合定义。
- 处理物品 i 时，任何最优解要么不选它保留旧 dp[c]，要么选它并由不含 i 的 dp[c-w] 加价值。
- 逆序使 dp[c-w] 尚属上一层，物品至多一次；归纳得到 0/1 最优。
复杂度
| Time | Space | Parameters |
|---|
| O(nC) | O(C) 压缩 | n 为物品数，C 为容量/目标；这是 pseudo-polynomial。 |
边界条件
- capacity=0
- weight=0
- 不可达 sentinel
- 负价值
- 计数取模
- 问恰好装满还是不超过容量
错误模式
| Pattern | Why it fails / fix |
|---|
| 0/1 容量正序 | 会读取本轮刚更新的 dp[c-w]，偷偷变成完全背包。 |
| 组合数与排列数混淆 | 物品外层通常数无序组合；容量外层可能让不同顺序分别计数。 |
| 不可达初始化为 0 | 最大值恰好容量时会把不存在方案当可行，应使用 -inf。 |
| 忽略 pseudo-polynomial | 复杂度依赖数值 C 而非其位数，C 巨大时不可接受。 |
选择与排除规则
- 先标明每项可用次数。
- 明确容量是上限还是必须恰好达到。
- 由复用规则决定容量循环方向。
- 检查 C 的数值大小，再决定是否用 O(nC)。
相关模板
| Relation | Template | Boundary |
|---|
| contrast | 子集 / 组合回溯 | 需要显式列出方案而不只是聚合答案。 |
原创微型例子
| 环节 | 内容 |
|---|
| Result | 0/1 最优为 9；正序更新可能错误地重复 (2,4)。 |
| Setup | 容量 5，物品为 (2,4)、(3,5)、(4,7)。 |
| Trace | 选前两项恰占 5、价值 9；单选第三项价值 7。 |
Recall prompts
我的补充