树形背包总结

(本文原作于2016年7月5日, 完善后以旧题重新发布, 旧文仍保留)

最近两天为树形背包问题所困扰。 这一切的起因是一年前在 HackerRank 上做的一道题 A Knapsack Problem 。

题目大意是:

给定一棵 $N$ 个节点的树，节点 $i$ 代表一件价值为 $v[i]$ ，体积为 $s[i]$ 的物品。另有一个体积为 $M$ 的背包，要求在树上选一个连通块装进背包，使得所选物品的总价值最大。

数据范围:

$ N, M le 2000 $

朴素的做法复杂度是$O(NM^2)$ ，TLE 。一直没看editorial，拖到现在。做这题之前我已看过崔添翼的《背包九讲》，期间又读了2009年国家集训队徐持衡的论文《浅谈几类背包问题》，徐的论文中提到树形依赖背包问题有 $O(NM)$ 解法，我很高兴，然而看了以后并不能懂。最近又想起这道题，再去翻徐的论文，折腾了两天，才发现:

• 徐的论文讲的比较简略，确实有点难懂
• 徐所讨论的树形依赖背包问题和 A Knapsack Problem 根本不是同一个问题

徐论文中所谓的树形依赖背包问题指的是：

给定一棵 $n$ 个节点的有根树，树的每个节点代表一件价值为 $v[i]$ ，体积为 $s[i]$ 的物品。另有一个体积为 $m$ 的背包，要求在树上选一个 包含根节点 的连通块装进背包，使得所选物品的总价值最大。

然而明确了这一点，我一时还是搞不懂徐持衡对此问题给出的 $O(nm)$ 的树形 DP 解法。又花了些功夫才基本弄懂：

$dp[i][j]$ 表示选择了节点 $i$ (及其所有祖先节点) (即根节点到 $i$ 的路径——记作 $P_i$ ——上的所有节点），此外再在 $P_i$ 的左侧和子树 $i$ 中选择总体积不超过 $j$ 的物品的最大价值。

(以上为旧文)

---

下面是【徐持衡论文中所描述的树形背包问题】(所谓 「具有树形依赖关系的背包问题」 ) 的两种做法

Solution I

来自 HackerRank 上此题的 editorial
将根节点记为 $u$ , 用 $size[v]$ 表示已 $v$ 为根的子树的节点个数, $vol[v]$ 表示节点 $v$ 所代表的物品的体积, $val[v]$ 表示其价值.
考虑 「节点的DFS序列」 $S$ , 在序列 $S$ 上进行 「背包」 (这里的「背包」是个动词).
$dp[i][j]$ : 在前 $i$ 个节点 (节点即物品) $S_1, S_2, dots, S_i$ 中选择一个「包含根节点（即 $S_1=u$） 且总体积恰为 $j$」 的连通块所能获得的最大价值

• 初始化 (边界条件, 初始条件)
  $dp[0][0]=0, dp[0][1dots m]=-infty$
  其余DP值初始化为 $-infty$

• 转移方程
  begin{align*}
  text{选 $S_i$ } &: dp[i-1][j-vol[S_i]]+val[S_i] to dp[i][j], && text{ where $j ge vol[S_i]$} \
  text{不选 $S_i$ } &: dp[i-1][j] to dp[i+size[S_i]-1][j]
  end{align*}

关于算法的正确性, 有以下结论:
$forall dp[i][j]>-infty$ 都满足题目要求的连通性条件.

为了证明的方便, 我们增加一个虚拟节点 $S_0=0$ ($val[0]=vol[0]=0$) 作为原根节点 $u$ 的父亲, 令 $S_0$ 为新的根节点.
我们要证明: 每个合法的DP状态对应的点集都是包含根节点 $S_0$ 的连通块.
(注意: 一个DP状态可能对应着多个选取点集的方案)
用归纳法.
只需证明第一个转移方程 ( $dp[i-1][j-vol[S_i]] to dp[i][j]$ ) 保持状态合法. 换言之, 我们要证明

$forall dp[i-1][j-vol[S_i]]>-infty$ 对应的点集都包含 $S_i$ 的父亲 $text{fa}[S_i]$.

证明:
从转移方程可得, $forall$ 对应于 $dp[i][j]$ 的点集 $V_{i,j}$ , $v notin V_{i,j} Longrightarrow$ 以 $v$ 为根的子树中的所有点都不在 $V_{i,j}$ 中.

若 $dp[i-1][j-vol[S_i]]$ 不包含 $text{fa}[S_i]$, 则在从边界情况 $dp[0][0]$ 转移到 $dp[i-1][j-vol[S_i]]$ 的过程中, 必然要对 $text{fa}[S_i]$ 或其某个祖先做出不选的决策, 经这一步将转移到 $dp[i'][j']$ ($i' ge i$). 矛盾!

Solution II

来自徐持衡的论文
这个做法和 Solution I 原理类似, 是递归实现的, 比较好懂一些.
$dp[i][j]$ 的含义如前上文所述。这个DP的求解并不能写成显示的转移方程，而是一个构建（consturction）过程。

vector<int> g[N];
solve(int u, int sum, int fa){
if(sum>m) return;
for(int i=sum; i<=m; i++){
dp[u][i]=dp[fa][i-s[u]]+v[u];
}
for(auto v: g[u]){
if(v==fa) continue;
solve(v, sum+s[v], u);
for(int i=sum+s[v]; i<=m; i++)
dp[u][i]=max(dp[u][i], dp[v][i]);
}
}

注：徐持衡论文中所定义的DP状态以及给出的实现都和这里略有不同，但思路是一样的。

总结

这两种做法思路上是相通的，复杂度都是 $O(nm)$。第一种做法尤为巧妙，很有启发性。