动态规划基础与 0/1 背包并列规则

0/1 背包是很多初学动态规划的人第一次真正接触“状态设计”的题型。难点不只是记住 dp[j] = max(...)，而是搞清楚状态表示什么、倒序枚举为什么必要、并列规则怎么塞进状态比较里。只要题目出现“每个对象最多选一次”“总容量不超过上限”“先最大化 A，再最小化 B”，就很可能已经进入背包 DP 的范畴。

学习目标

学会识别 0/1 背包题面。
学会定义“容量限制下的最优状态”。
学会处理不可达状态和倒序枚举。
学会在背包里加入并列规则，而不只比较单个数值。

什么样的题是 0/1 背包

通常有这些特征：

有 n 个候选对象。
每个对象最多选一次。
每个对象占用一定容量，如时间、预算、体力、空间。
目标是在容量不超过上限的前提下，使价值最大。

题库对应：

红色讲解队编组：训练时长内积分最大化

这道题不只要求最大积分，还要求在积分相同的情况下：

总时长更小。
若总时长也相同，入选人数更少。

这就是“并列规则进入状态比较”的典型场景。

动态规划到底在做什么

动态规划不是“暴力试完所有方案”，而是把大量重复子问题折叠成状态表。

在 0/1 背包里，最常见的状态是：

dp[h] 表示“总时长恰好为 h 时，当前能得到的最好结果”。

如果只比积分，那么 dp[h] 存一个整数即可。

如果还要带并列规则，就要把状态扩成一组信息，例如：

score
used_hours
team_size

为什么初始化最难

很多背包题的 bug 出在初始状态不清楚。常见正确做法是：

只有 dp[0] 可达，表示“什么都不选，价值为 0”。
其他容量初始为不可达。

NEG = -10**18
dp = [(NEG, 0, 0)] * (H + 1)
dp[0] = (0, 0, 0)

更稳的写法是用 None 表示不可达，比较时先判断是否可达。

为什么必须倒序枚举容量

0/1 背包中，每个对象只能选一次。如果你正序枚举容量，当前对象刚更新出来的新状态，可能会在同一轮里再次被自己使用，等于把同一个对象重复选了多次。

倒序枚举的意义就是：本轮更新只基于“上一轮还没用当前对象的状态”。

for cost, value in items:
    for h in range(H, cost - 1, -1):
        dp[h] = max(dp[h], dp[h - cost] + value)

并列规则怎么放进状态比较

s2-jh-08 的优先级是：

积分最大
若积分相同，总时长最小
若前两项都相同，人数最少

所以状态比较函数可以写成：

def better(a, b):
    if a.score != b.score:
        return a.score > b.score
    if a.hours != b.hours:
        return a.hours < b.hours
    return a.team_size < b.team_size

这里的关键不是语法，而是明确“主目标”和“次目标”的顺序。顺序错了，整个 DP 的最优定义就错了。

一维背包怎么保留多维信息

虽然容量维度只有一维，但每个 dp[h] 可以存一个结构体或元组：

score：当前总积分
hours：当前已用时长，通常就是 h
team_size：当前选了多少人

转移时，从 dp[h - cost] 推到 candidate，再和 dp[h] 比较。

最终答案为什么不能只看 `dp[H]`

题目要求的是“总时长不超过 H 时的最优解”，不是“恰好等于 H 时的最优解”。因此最后要在 0..H 的所有可达状态里，再按同一套比较规则挑一次最优答案。

这一步经常被忽略，结果程序只看了容量上限位置，漏掉了更小容量下的更优方案。

常见错误

正序枚举导致重复选取

这是 0/1 背包最常见的错误之一。

不可达状态也参与转移

若 dp[h - cost] 本身不可达，就不应该继续生成候选状态。

并列规则前后顺序写反

例如本该“积分优先”，结果写成“时长优先”，整体答案就会偏掉。

只记录分值，不记录附加指标

如果题目还要最小总时长、最少人数，单独存一个分数不够。

与贪心的边界

很多选择题看上去都像“挑最值”，但只要存在总容量限制，且对象之间需要组合，就要先怀疑是不是背包，而不是贪心。s2-jh-08 就是典型例子：按积分密度或按单项积分贪心都不可靠，因为全局最优可能来自不那么显眼的组合。

与题库的联系

`s2-jh-08`

练的是 0/1 背包的一维压缩。
同时训练多关键字状态比较。
最后还要从整张状态表提取最终答案，而不是只看一个位置。

训练建议

第一次做背包题，先画一个很小的 dp 表手推 3 到 4 个物品。
写代码前先把“状态定义”和“比较规则”写成一句自然语言。
如果题目里写着“每个对象最多选一次”，就先检查你的循环是不是倒序。
做完后专门构造“同分但时长不同”“同分同时长也相同但人数不同”的测试，验证 tie-break 是否真的生效。