将树形01背包优化到O(n*m)

有先决条件的背包问题通常是树形DP的一个典型问题。

常见的例题有选课（洛谷P2014、Vijos 1180）

这类问题的定义是，在背包中，我们需要先选某个物品，才能选择这个物品的子物品。最后求出在花费满足限制的情况下，实现最大的价值。

实际生活中的例子有选课、买家具等。

朴素的做法就是用邻接表将树存下来，然后用DFS去深度优先遍历这棵树。

DP方程如下

f[father][j] = max(f[father][j],f[father][j–k]+f[child][k–cost[child]]+weight[child]);

其中father为当前节点，child为这个节点的一个子节点。

不难看出这个需要两重循环，我们对于f[father][j]这个状态需要去枚举k一次次取max来求解最优问题。

相当于，我们需要枚举，对于这个物品我们需要使用它和它的子物品多少价值。

这样做出来的时间复杂度就是O(n*(m^2) )

尽管大部分题目对于这样的时间复杂度是会放水的。

但是后来，有一次我想用树形DP去解决NOIP2006 提高组T2 P1064 金明的预算方案的时候，却发现了问题。

这样的写法，只拿了30分，后面的点全TLE了。

那道题的题目描述大概是，购买物品，每个物品有所属主件或没有所属主件，每个主件有0-2个子物品。

给出预算和每个物品的花费和价值(和题目描述有点不一样但是乘起来一个意思)，求出最大价值和。

数据范围，预算<=32000，物品<=60。

这种情况下如果使用O(n*m^2)的算法，显然1s时限是无法通过的。

当然这种问题可以不用树形DP解决，但我后来交了这份TLE的代码之后，我去网上搜索相关题解，发现了一个这类问题的优化做法。

我看到了2009年国家集训队论文，来自浙江省温州中学徐持衡《浅谈几类背包题》。讲到了一个优化算法。大概意思就是，我们把父亲节点的f数组复制给子节点，并把子节点的这一行数组就加上子节点的权值。

相当于这样：f[child][j] = f[father][j]+weight[child]

这样做了以后，我们就相当于把下一层默认了走这棵树的指定路径，包括走当前节点。

之后对子节点进行dfs，顺带更新这个数组，调用栈回到父亲节点这层之后，对父亲节点进行更新，采用以下方程。

f[father][j] = max(f[father][j],f[child][ j–cost[child] ])

这样，这个问题就被我们轻松地优化成了O(n*m)的算法。

c语言代码如下：

[sourcecode language=”c”]
void dfs(int cur,int maxp) {//p是当前物品的价格,w是价值,maxp是当前这个物品需要计算的最大花费
for (int i=head[cur];i != -1;i = e[i].next) {
if (maxp <= e[i].c) continue;
for (int j=0;j<=maxp-e[i].c;j++)
f[e[i].v][j] = f[cur][j] + e[i].w;
dfs(e[i].v,maxp-e[i].c);
for (int j=maxp;j>=e[i].c;j–)
f[cur][j] = max(f[cur][j],f[e[i].v][j-e[i].c]);
}
}
[/sourcecode]

你也可以参考我的选课代码。

https://github.com/cyyself/OILife/blob/master/Luogu/P2014%20%E9%80%89%E8%AF%BE.cpp