树形依赖背包是指所有物品形成了相互依赖关系(即选了A就必须选B)的背包问题.一般这种依赖关系都是树形的(如果不是就只能用网络流搜索),所以这种背包问题也叫树形背包问题.
树形背包可以套用最大权闭合图的算法搜索来做,但是这种算法的复杂度过高,徐持衡大牛在他2009年的论文中提出了一种O(NV)的算法,可以有效地解决这类问题.这篇文章可以看做该论文的简化版,建议想要更加深入了解的同学去看一下徐持衡的论文.
先看一道题目(直接贴图片):
选课
其中,m<=1000,n<=m;
[解决]这是一道典型的树形背包,我们先将多叉树转成二叉树,再进行DP.
一般的背包是要令f[I,j]表示前i个物品选取体积共为k的物品所能得到的最大价值.然而这样进行dp,时间复杂度最低也是O(NC*C)的,因为合并两个泛化物品的最低复杂度是O(c)的.
那么,我们应该怎样进行DP呢?
注意到树形背包与普通背包最大的不同就在于它具有依赖性,只要消去这种这种依赖性,那么我们就能像普通背包那样O(NC)地求解了.
怎样消除这种依赖性呢?
由于树结构的特征,所有节点都只有一个前驱,所以,我们可以在对一个物品进行DP时,强制把他的前驱加进背包!
这样,我们得到一个递归的过程:
Procedure Deal(rt,v)
J=l[rt]
While j<>nil
For i=0 to v-w[rt]do
F[j,i]=f[rt,i]+p[j]//1
Dfs(j,v-w[rt])//2
For i=w[rt] to v do
F[rt,i]=max(f[rt,i],f[j,i-w[j]]);//3
J=r[j]
过程中,1即为将j强制加入其子树子节点的过程.2为递归的过程,3为利用子节点的值更新父节点的过程.在递归调用的过程中,先将父节点的信息全部加入子节点中,再对子节点进行递归处理,最后用子节点返回的信息来更新父节点.
这种算法的复杂度不难分析,每种状态会从父节点收到信息,再将信息返回父节点,所以总的复杂度为O(NC).接下来我们说明算法的正确性.
首先要明确的一点是:f[I]在这里不再表示以i为根的子树的状态,而是表示从根到i的路径的左边的所有节点及i的子树的信息.即下图(此图略丑,意会一下就行了)被圈出来的部分.
首先,叶节点的状态肯定是正确的,这可以从转移的过程得出.其次,考虑一个根节点,若它的子节点的状态时正确的,显而易见的是,他的状态最终也会变成正确的,这可以通过观察第3步得出.
明白了dp的过程后,程序就很好写了.
代码如下(徐持衡的):
接着,让我们再看一道题目:
有线电视
【问题描述】
某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构，这棵树的根结点位于足球比赛的现场，树叶为各个用户终端，其他中转站为该树的内部结点。
从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的，一场转播的总费用等于传输信号的费用总和。
现在每个用户都准备了一笔费用想观看这场精彩的足球比赛，有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。
写一个程序找出一个方案使得有线电视网在不亏本的情况下使观看转播的用户尽可能多。
【输入】
输入文件的第一行包含两个用空格隔开的整数N和M，其中2<=N<=3000,1<=M<=N-1,
N为整个有线电视网的结点总数，M为用户终端的数量。
第一个转播站即树的根结点编号为1，其他的转播站编号为2到N-M，用户终端编号为N-M+1到N。
接下来的N-M行每行表示一个转播站的数据，第i+1行表示第i个转播站的数据，其格式如下：
K A1 C1 A2 C2 …… Ak Ck
K表示该转播站下接K个结点（转播站或用户），每个结点对应一对整数A与C, A表示结点编号，C表示从当前转播站传输信号到结点A的费用。最后一行依次表示所有用户为观看比赛而准备支付的钱数。
【输出】
输出文件仅一行，包含一个整数，表示上述问题所要求的最大用户数。
【解决】
这道题有其他做法,但也可以看做树形背包,这里只讨论他的树形背包做法.首先根据题目描述建立一棵树,每个叶节点的体积为1,价值为p[i]-cost[i],非叶节点体积为0,价值为-cost[i].求出取各个体积时最大的费用即可求出在不亏本的情况下的最大用户数.接着直接从后往前扫一遍就可以得出答案.
代码如下(我的):
program tele;
type
int=longint;
const
oo=99999999;
var
i,j,k,m,n:int;
l,r,p,w:array[-1..3000]of int;
f:array[-1..3000,0..3000]of int;
x,y:int;
function max(x,y:int):int;
begin
if x>y then exit(x)
else exit(y);
end;
procedure dfs(rt,v:int);
var i,j:int;
begin
if v<1 then exit;
j:=l[rt];
while j<>-1 do begin
for i:=0 to v do f[j,i]:=f[rt,i];
dfs(j,v-w[j]);
for i:=1 to v do f[rt,i]:=max(f[rt,i],f[j,i-w[j]]+p[j]);
j:=r[j];
end;
end;
begin
assign(input,'tele.in');reset(input);
assign(output,'tele.out');rewrite(output);
fillchar(l,sizeof(l),$FF);
f[1,0]:=0;r[-1]:=-1;
read(n,m);
for i:=1 to n-m do begin
read(k);
for j:=1 to k do begin
read(x,y);
r[x]:=l[i];l[i]:=x;
p[x]:=-y;
end;
end;
for i:=1 to m do begin
read(x);
inc(p[n-m+i],x);
f[1,i]:=-oo;
w[n-m+i]:=1;
end;
dfs(1,m);
i:=m;
while (f[1,i]<0) do dec(i);
write(i);
close(input);close(output);
end.
需要留心的是f[1]的初值,想一想为什么要这么赋值.
细心的同学可能会注意到,我的过程与徐持衡的不同,但两者是完全等价的,效率上也没有很大的区别.树形背包的基本算法就是这样.具体的题目中,往往会给你一棵树,然后给每个节点一个权值之类的东西和一些限制,然你求这么选得到最大/最小收益,这种题目就有可能是树形背包的模型.
BY QW
转载请注明出处