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

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

常见的例题有选课(洛谷P2014、Vijos 1180)

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

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

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

DP方程如下

f[father][j] = max(f[father][j],f[father][jk]+f[child][kcost[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][ jcost[child] ])

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

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]);
    }
}

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

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

在 “将树形01背包优化到O(n*m)” 上有 1 条评论

  1. 何森的论文《浅谈数据的合理组织应用与研究》里面的算法4也是O(nm)算法,没有在树上dp,而是在树的先序遍历上dp,感觉更妙也更好懂。

发表评论

电子邮件地址不会被公开。 必填项已用*标注