树形依赖动态规划

前端之家收集整理的这篇文章主要介绍了树形依赖动态规划前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

定义

树形依赖动态规划一般为背包问题,依赖就是指儿子依赖于父亲的树形动态规划,一般形式为只有选择了父亲节点才能选择儿子节点,对于这一种特殊的树形动态规划,有一种时间复杂度十分优秀的的方法可以解决此类问题。

举个例子

先来一道例题,给出一棵有 @H_403_17@n 个点的树, 1 为根节点,选择第 i 个点的价值为 Vi ,付出的代价为 Pi ,只有选择了父亲节点才可以选择其儿子节点,最多可以付出的总代价为 M @H_403_175@M,在不违反上述规定的条件下求最大化的总价值。
N , M 2 * 103

普通做法

@H_70_301@fi,j 表示选择以 i 为根的这一棵子树,花费了 j 的代价时所能获得的最大代价。转移就很显然了分别枚举在i的所有儿子花费的代价,最后把自己选上即可。
由于每次合并的复杂度为 M2 ,总共合并 N 次,所以总时间复杂度为 O ( N M2 )。

{
    int i,j,l,k;
    fo(i,1,g[o])dg(son[o][i]);
    fo(i,g[o])
    fd(j,m-P[o],P[son[o][i]])
    fo(l,P[son[o][i]],j)
    f[o][j]=max(f[o][j],f[son[o][i]][l]+f[o][j-l]);
    fd(i,m,P[o])f[o][i]=f[o][i-P[o]]+V[o];
}

特殊做法

上述做法显然会超时。
我们分析一下为什么这样做时间复杂度这么大了,每一次合并的时间复杂度为 M2 ,如果可以每次转移都能做到 M 的时间复杂度,那总时间复杂度就是 O ( NM ),接下来就给出这种做法的具体做法。
首先求出整棵树的 dfs 序,并求出以 i 为根的字数大小 sizei
fi,j 表示选到 i 个点时花费的代价为j时所能获得最大的价值,第 i 个点可选可不选。
按照 dfs 序从后往前做,如果当前点i不选,则第一个转移为 fi,j = fi+sizei,j ,表示继承它后一个兄弟的状态(兄弟即指它父亲的其他儿子)。
如果当前选择第 i 个点,则从 i 的对应的 dfs 序的下一位(记为 k )转移过来,即 fi,j = min ( fi,j , fk,jPi + Vi ),仔细思考一下便可发现这样转移是正确的。

给出一张转移的简略草图,帮助理解。
注,黄色线表示第一种转移,即不选择第i个点的转移,红色线为第二种转移。

猜你在找的设计模式相关文章