Ⅶ · 依赖背包 · 两步化归

依赖背包：附件依附主件

物品之间有依赖：某些物品（附件）只有在选了它所依附的主件时才能选。例：买了「台式机主机」才能加装「SSD」「内存条」；没买主机，附件无意义。直接枚举每个主件的「附件子集」会指数爆炸，标准解法是两步化归——把它化归为已解决的 01 背包（第 1 讲）与分组背包（第 6 讲）；再把依赖从「一层」推广到「多层树」，就是树形 DP。

Stage A · 对每个主件 k 的附件集做 01 背包 → Fₖ[s] =「给附件 s 元时的最大附加价值」
Stage B · 把「主件 + 附件预算 s」当分组背包的候选：F[v] ← maxₛ F[v − Cₖ − s] + Wₖ + Fₖ[s]

1 · 应用案例 · 装机预算分配

两棵依赖树：台式机与笔记本。每件物品有费用 C 与价值 W，附件必须依附于主件方可选取。下面分两步演示。先看 Stage A 给每个主件预处理出 $F_k$ ，再看 Stage B 用它做分组背包；算完后被选中的主件 / 附件会在树上点亮。调整预算 V，带深色填充的节点即为 DP 选中的物品。

NOTES · 简化版的完整手算流程(V = 15)

设容量 V = 15，主件 A 满足 (Cₐ, Wₐ) = (4, 10)；三个附件 a₁, a₂, a₃ 均依赖于 A，参数依次为 (C, W) = (2, 3), (3, 4), (5, 8)。

第一步 · 对附件集合执行 01 背包。定义 Fₐ[v] 为「在附件集合上花费不超过 v 时的最大价值」，v ∈ [0, V−Cₐ] = [0, 11]。按标准 01 背包对 a₁, a₂, a₃ 逐次处理得：

Fₐ = [0, 0, 3, 4, 4, 8, 8, 11, 12, 12, 15, 15]
 v =  0  1  2  3  4  5  6   7   8   9  10  11

例如 Fₐ[8] = 12 对应选 a₂+a₃（费用 3+5=8、价值 4+8=12）;Fₐ[11] = 15 对应选全部三个附件（费用 2+3+5=10 ≤ 11、价值 3+4+8=15）。

第二步 · 执行分组背包。将「主件 A + 附件子集」视为一个物品组，组内候选按附件花费 s ∈ [0, V−Cₐ] 索引。候选 s 的总费用 = Cₐ+s、总价值 = Wₐ+Fₐ[s]:

s = 0  → (费用 4,  价值 10 + 0  = 10)
s = 2  → (费用 6,  价值 10 + 3  = 13)
s = 5  → (费用 9,  价值 10 + 8  = 18)
s = 11 → (费用 15, 价值 10 + 15 = 25)

执行分组背包后，F[15] = 25，对应方案：选主件 A 与全部三个附件（总费用 4+2+3+5=14 ≤ 15、总价值 10+3+4+8=25）。

它就是经典竞赛题。NOIP2006「金明的预算方案」正是这个模型（主件 = 大件电器、附件 = 配件）。把依赖从「一层」推广到「多层树」，就是树形背包 / 树形 DP：每个节点向上汇报「分配给我这棵子树 s 元时的最优值」，本质仍是「在子树上做一遍分组背包」——这正是 §2 / §3 要展开的。

2 · 两步化归方法 · 算法的四步推导

指数级的「附件子集」枚举可经两次化归消解：先对每个主件的附件集合执行 01 背包，得到「花费不超过 v 时附件的最大价值」；再将「主件 + 不同附件组合」打包为分组背包（第 6 讲）的一个物品组。下面把这条思路拆成四步推导。

NOTES · 一般情形 · 树形 DP 的递归结构

对附件集合做 01 背包得 Fₖ[v]；抽象上 Fₖ 即「附件子集」这一物品族的「代表」——它把多件原始物品压成一件以 v 为参数的「函数物品」。当附件本身有附件时，递归套用同一压缩：每个子树都被压成一件以「分配给子树的预算」v 为参数的泛化物品。

记号上用 h_T 表示这件「子树压缩物品」——以 T 为根的子树上、花费不超过 v 时的最大价值记作 h_T(v)；它包含 T 本身（代价 C_T、价值 W_T），这点与简化版中「仅附件」的 Fₖ 互补。当 T 是单纯主件 k 时，h_T(v) = Wₖ + Fₖ[v−Cₖ](v ≥ Cₖ 时)、0（v < Cₖ 时），恰是 2.2 中分组背包看到的物品形式。这一抽象将在第 8 讲（泛化物品）正式形式化。

当依赖深度大于 2 时（附件本身可作子主件，拥有自己的附件），问题成为森林上的树形 DP。例如：

        主件 A
       /  |  \
      B   C   D
     / \
    E   F

按后序遍历（DFS · 先子后父递归）处理，完整次序为 E → F → B → C → D → A：进入 A 的第一棵子树 B，先求叶 h_E、h_F，再合并 B 自身与 {h_E, h_F} 得 h_B；然后回到 A，进入 C（单点叶）；接着 D（单点叶）；最后在根 A 合并 A 自身与 {h_B, h_C, h_D} 得 h_A，而 h_A(V) 即答案。注意是递归意义上的次序（处理完一整棵子树才进入下一棵），而非「叶子全列前、内部节点列后」的分层顺序。

关键性质。每个非叶节点的 DP 函数仅依赖于其所有子节点的 DP 函数。后序遍历恰好保证「先子后父」的求值次序：若反过来先处理父节点 T，其各子树贡献 h_child 尚未计算，h_T 无从合并。所以后序遍历不是约定，而是数据依赖关系的唯一允许次序——这正是第 8 讲泛化物品之和的递归形式。

复杂度。简化版（每主件至多一层附件）：各主件附件 01 预处理 O(NV)，再以 K 个主件分组背包 O(KV²),总 O(NV + KV²)。树形版（任意深度）：每个非叶节点合并自身与所有子树 DP 函数 O(V²),N 个节点合计 O(NV²)。当 V 较小（如 V ≤ 10³）均可实用；V 较大时需单调队列、卷积加速。

方法论意义。面对复杂问题，与其堆砌特殊处理代码，不如退后一步重新审视抽象层次。「将主件附件视为物品组」即是一例——它把看似新颖的依赖结构，化归为既有的分组背包框架。这呼应第 4 讲（混合背包）的开闭原则：新约束应通过「复用既有抽象的组合」而非「另起炉灶」来吸收。

NOTES · 记号约定 · 出处 · 延伸阅读

子树代表函数。本讲用 h_T(v) 表示「费用不超过 v 时，从以 T 为根的子树中选取（必须先选 T 自身）所能取得的最大价值」，定义在 v ∈ [0, V] 上，以数组存储。后序遍历保证「先子后父」的求值次序——这是数据依赖关系的唯一允许次序，而非约定。

关键概念出处。依赖背包在英文文献中称为 knapsack problem with precedence constraints / precedence-constrained knapsack。精确求解可参见 You & Yagiura, A reformulation-linearization technique-based heuristic, 2013。工程中依赖结构常以「主件-附件」或「父任务-子任务」出现，广泛见于项目管理(PERT/CPM)、流水线调度与软件套餐设计。

延伸阅读。更一般形式是带约束背包问题(constrained knapsack problem)。当依赖不是树形而是 DAG 时，问题变为 NP-hard 且无伪多项式算法，参见 Goldberg & Marchetti-Spaccamela, A General DP Approach to Constrained Knapsack Problems。实践中 DAG 约束通常借助拓扑序展开为树或线性序列后求解。

通向第 8 讲 · 泛化物品。第 8 讲将正式定义泛化物品：一件物品由函数 h(v) 刻画，输入费用、返回价值。本讲的「子树代表函数 h_T」正是泛化物品的具体实例——每个子树在背包模型中等价于一件泛化物品。

3 · 树形 DP · 深度不一致的实例推演

当附件本身又能有附件时，依赖关系呈现一棵任意深度的树（甚至森林）。本节给一棵 8 节点不规则深度树 作样例，按后序遍历推演每个节点的 h_T(v) 数组——展示算法如何把不同深度的子树统一压缩成同一种「h 函数」形态，父节点合并时不再关心深度差异。本节是 §2 末「一般情形 · 树形 DP」抽象论述的具体数字实例。

NOTES · 关键步骤验算 · h_B 的合成过程

本节最复杂的合成是 h_B，因为 B 有两个叶子 E 和 F。完整推演：

1. 先合并子树森林 h_EF(v) = max(h_E(v_E) + h_F(v_F)) over v_E+v_F=v:

v = 0: h_E[0] + h_F[0] = 0 + 0 = 0
v = 1: max(h_E[1]+h_F[0], h_E[0]+h_F[1]) = max(1, 2) = 2
v = 2: max(h_E[2]+h_F[0], h_E[1]+h_F[1], h_E[0]+h_F[2]) = max(1, 3, 2) = 3
v ≥ 2: 都是 3 (= 选 E + F, 费用 2, 价值 1+2=3)

2. 再加 B 自身(C_B=2, W_B=4):

v < 2:  h_B = 0 (B 自身放不下)
v = 2:  h_B = 4 + h_EF[0] = 4 + 0 = 4 (只选 B, 不带子)
v = 3:  h_B = 4 + h_EF[1] = 4 + 2 = 6 (B + F)
v = 4:  h_B = 4 + h_EF[2] = 4 + 3 = 7 (B + E + F)
v ≥ 4: 7 (再多预算也无法添加价值)

h_B = [0, 0, 4, 6, 7, 7, 7, 7, 7]. 同样的合并模式（子树森林 + 自身）也用于 h_D 和 h_A，只是子树数 / 深度不同。

复杂度 · 后序遍历的代价。每个内部节点合并 k 个子树森林需 O(V²)（类似分组背包二维卷积，k 次共享 V 轴）;N 个节点合计 O(NV²) 时间，空间 O(NV)。当 V ≤ 10³ 时可实用。

与 §1 / §2 的关系。§1 的「简化版」（主件 + 一层附件）是本节特例：当依赖树深度 ≤ 2 时，h_T 退化为 W_k + F_k[v−C_k](即 §1 Stage B 的组内候选)。一旦深度 ≥ 3，就需要本节的递归形式。§1 的两阶段(Stage A + Stage B)是 §3 树形 DP 的「两层特例」，§3 是 §1 的一般化推广。

4 · 应用案例 · 会员卡 + 品类券 + 单品券

§1 装机案例与 §2 / §3 的方法论，在电商会员体系有一个深度更深的真实落地——三层依赖：必须先开会员卡（主件），才能领品类券（中间层附件），才能在符合品类的单品上叠加单品立减券（叶子附件）。这正是 PLUS / 88VIP / 拼多多月卡等会员体系的真实计费链条。本节每棵树深度 = 3（根 + 中间层 + 叶子），是 §3 树形 DP 的真实落点——求解需后序遍历：先叶子，再中间，再根，每个节点把自身与所有子树的「h_T(v) 函数」合并成新的 h。

NOTES · 为何 V=500 时 DP 偏向 88VIP 的深层投资 · 跨树预算分配

V=500 时双卡开通后余 ¥312。DP 的决策：把全部余额投到 88VIP 美妆品类 + 面霜 + 口红 共 ¥310，减免 ¥57;PLUS 这一侧只开卡。读者可能问：PLUS 服饰品类(¥100) + 卫衣(¥50) 加起来才 ¥150、减免 ¥30，性价比 30/150 = 0.20，似乎不弱于 88VIP 深层路径 57/310 ≈ 0.184，为什么 DP 不混合两棵树？

原因仍是分配粒度：任何混合方案在 ¥312 余额下都凑不出更高的总减免——分给 PLUS 服饰链一部分后，剩余给 88VIP 的预算就装不下「美妆品类券 + 面霜」这条更值的深链，只能退而领品类券，合计反而不及纯 88VIP 路径的 57。把 V 调到 ≥ 800 即可观察 DP 转向「两棵树同时展开三层」——这是预算够大、不再需要在树间竞争的临界点。这个临界点的存在，正是树形 DP 与简单贪心的本质区别：贪心按局部性价比排序，而树形 DP 在全局上评估「开通某棵树 + 投资多深」的总收益。

NOTES · 与 §1 装机 / §3 树形 DP 的关系

本节的算法不是新算法，而是 §3 树形 DP 在真实场景的具体实例:

§1 装机（深度 = 2）：两步化归（Stage A 附件 01 + Stage B 主件分组背包）即可解决——这是 h_T 抽象的退化形式，因为附件无子；
§3 抽象推演（深度可任意）：用 h_T(v) 后序遍历，把任意深度子树压成「一件泛化物品」——但 §3 用 8 节点教学样例，无实际语义；
§4 本节（深度 = 3）：给 §3 的 h_T 算法配一个真实场景，让读者看到「会员卡 → 品类券 → 单品券」三层依赖如何被同一抽象自然处理。

这种「用同一抽象处理不同深度」的统一性，是依赖背包（及其推广：第 8 讲泛化物品）的核心价值。每个子树等价于一件「以 v 为输入、以最大价值为输出」的函数式物品——本节的会员卡 / 品类券 / 单品券都是这类函数式物品的具体实例。