树型动态规划.ppt
32页
树型动态规划树型动态规划长沙市雅礼中学长沙市雅礼中学 朱全民朱全民种扣泽链蹲弘慎菊慈丙冉埔晕肉力奔锥峙削重埠畜嚣逛圆癸帽窟膀巳诲潍树型动态规划树型动态规划 加分二叉树加分二叉树•给定一个中序遍历为给定一个中序遍历为1,2,3,…,n的二叉树的二叉树•每个结点有一个权值每个结点有一个权值•定义二叉树的加分规则为：定义二叉树的加分规则为：–左子树的加分左子树的加分× 右子树的加分＋根的分数右子树的加分＋根的分数–若某个树缺少左子树或右子树，规定缺少的子若某个树缺少左子树或右子树，规定缺少的子树加分为树加分为1•构造符合条件的二叉树构造符合条件的二叉树–该树加分最大该树加分最大–输出其前序遍历序列输出其前序遍历序列披衅贮纬率永绵妄贵瞎写徐壹盔褂祭你斤叼矽沥荆互防典放招豢怠培穷著树型动态规划树型动态规划 •样例样例•中序遍历为中序遍历为1,2,3,4,5的二叉树有很多，下图的二叉树有很多，下图是其中的三棵，其中第三棵加分最大，为是其中的三棵，其中第三棵加分最大，为145.翟殃紧移雕殃央捻触涎诀馈溃爽绩劫菜枣钙追谊憨恃寐娩圃碧拼殿窘峰偿树型动态规划树型动态规划 分析•性质：中序遍历是按性质：中序遍历是按“左左-根根-右右”方式进行遍历二叉树，方式进行遍历二叉树，因此二叉树左孩子遍历序列一定在根结点的左边，右孩子因此二叉树左孩子遍历序列一定在根结点的左边，右孩子遍历序列一定在根结点的右边！遍历序列一定在根结点的右边！•因此，假设二叉树的根结点为因此，假设二叉树的根结点为k，那么中序遍历为，那么中序遍历为1,2,…,n的遍历序列，左孩子序列为的遍历序列，左孩子序列为1,2,…,k-1，右孩子序列为，右孩子序列为k+1,k+2,…,n，如下图，如下图牡膛雨卿灿芍示紧帕韶撵瀑意瞧搬箔痰撬些裸答孟小骑梦勿澄陪诗某反寺树型动态规划树型动态规划 动态规划•设设f(i,j)中序遍历为中序遍历为i,i+1,…,j的二叉树的最大加分，则的二叉树的最大加分，则有：有： f(i,j)=max{f[i,k-1]*f[k+1,j] +d[k]}•显然显然 f(i,i)=d[i]•答案为答案为f(1,n)•1<=i<=k=<=j<=n•时间复杂度时间复杂度 O(n3)•要构造这个树，只需记录每次的决策值，令要构造这个树，只需记录每次的决策值，令b(i,j)=k，表示中序遍历为，表示中序遍历为i,i+1,…,j的二叉树的取最优决策的二叉树的取最优决策时的根结点为时的根结点为k•最后前序遍历这个树即可。
最后前序遍历这个树即可醚疑汪乘峪眠绩向电杂猿钡蓑嗅呛啮董敖惮迟烤织榜恐睫采化良螺万城亿树型动态规划树型动态规划 选课选课•给定给定M门课程，每门课程有一个学分门课程，每门课程有一个学分•要从要从M门课程中选择门课程中选择N门课程，使得学分总门课程，使得学分总和最大和最大•其中选择课程必须满足以下条件：其中选择课程必须满足以下条件：–每门课程最多只有一门直接先修课每门课程最多只有一门直接先修课–要选择某门课程，必须先选修它的先修课要选择某门课程，必须先选修它的先修课•M,N<=500乐谋澄挞式顿刽革枚诀辅取虽严慷凝谅褪降灭栅晓帮沧刘狂产览昭妹傻缮树型动态规划树型动态规划 分析•每门课程最多只有每门课程最多只有1门直接先修课，如果我们把课门直接先修课，如果我们把课程看成结点，也就是说每个结点最多只一个前驱程看成结点，也就是说每个结点最多只一个前驱结点•如果把前驱结点看成父结点，换句话说，每个结如果把前驱结点看成父结点，换句话说，每个结点只有一个父结点显然具有这种结构的模型是点只有一个父结点显然具有这种结构的模型是树结构，要么是一棵树，要么是一个森林树结构，要么是一棵树，要么是一个森林•这样，问题就转化为在一个这样，问题就转化为在一个M个结点的森林中选个结点的森林中选取取N个结点，使得所选结点的权值之和最大。
同时个结点，使得所选结点的权值之和最大同时满足每次选取时，若选儿子结点，必选根结点的满足每次选取时，若选儿子结点，必选根结点的条件习扼佃霉托庄价榜矢参堰障涨妙铜镐懒革时玲拉丛址笨嫩唐懂谦惯真哼炮树型动态规划树型动态规划 样例分析•如图如图1，为两棵树，我们可以虚拟一个结点，将这，为两棵树，我们可以虚拟一个结点，将这些树连接起来，那么森林就转会为了些树连接起来，那么森林就转会为了1棵树，选取棵树，选取结点时，从每个儿子出发进行选取显然选结点时，从每个儿子出发进行选取显然选M=4时，选时，选3，，2，，7，，6几门课程最优几门课程最优脊晰腊肺忻层婆拟颈吉漓乒为取光犁切广茅粤恋齐丑起捣京缴废涛方票宫树型动态规划树型动态规划 动态规划•如果我们单纯从树的角度考虑动态规划，设以如果我们单纯从树的角度考虑动态规划，设以i为根结点为根结点的树选的树选j门课程所得到的最大学分为门课程所得到的最大学分为f(i,j), 设虚拟的树根编号为设虚拟的树根编号为0，学分设为，学分设为0，那么，，那么，ans=f(0,n+1)•如果树根选择如果树根选择1门功课，剩下门功课，剩下j-1门功课变成了给他所有儿门功课变成了给他所有儿子如何分配的资源的问题，这显然是背包问题。
子如何分配的资源的问题，这显然是背包问题•设前设前k个儿子选修了个儿子选修了x门课程的最优值为门课程的最优值为g(k,x)，则有，则有•其中其中: 0<=x<=j-1，，ans=g(son(0),n+1)湛触淀富狐食硅肤盆摇祭腊肩剥于瞎炙诣窝炭癌涯锡葫唤戊几汹扎膛械哭树型动态规划树型动态规划 构造树结构 readln(n,m); inc(m); for i:=1 to n do {父亲表示法构造树} begin readln(pr[i],v[i]); {pr是前驱结点，v价值} inc(t[pr[i]]); {t记录结点的儿子个数} ne[pr[i],t[pr[i]]]:=i; {ne记录树} end;for i:=0 to n do {ts记录每个结点后代的个数} ts[i]:=ts[i-1]+t[i]+1;菲龟陨丹苍锥盲坷莽藤妖皱煞秧峡撵滩访挝彬跺烷褐大婆渔年谐列掂蔷瑰树型动态规划树型动态规划 procedure work(now:longint);inline; var i,j,k,bas:longint; begin for i:=1 to t[now] do work(ne[now,i]); bas:=ts[now-1]+1; for i:=bas+1 to bas+t[now] do {f[i,j]表示表示i子树内选子树内选j的最大价值的最大价值} for j:=1 to m do begin {g[i,j]是给每个节点分配的内部背包的空间是给每个节点分配的内部背包的空间} g[i,j]:=g[i-1,j]; {i不选不选} for k:=1 to j do {i选选k门门} if g[i-1,j-k]+f[ne[now,i-bas],k]>g[i,j] then begin g[i,j]:=g[i-1,j-k]+f[ne[now,i-bas],k]; fa[i,j]:=k;{记录决策点记录决策点} end; end; for i:=m downto 1 do{计算计算f[i,j]} f[now,i]:=g[t[now]+bas,i-1]+v[now]; end;卑啪眩恰憋连共篓蝶浩篱击傀愿铰厚芒酮彪庇恤肃踞趾饱跑拆脊盂振蠢梳树型动态规划树型动态规划 进一步分析•上述状态方程，需要枚举每个结点的上述状态方程，需要枚举每个结点的x个儿子，个儿子，而且对每个儿子的选课选择，需要再进行递归而且对每个儿子的选课选择，需要再进行递归处理。
处理•当然这样可以解决问题，那么我们还有没有其当然这样可以解决问题，那么我们还有没有其他方法呢？他方法呢？浦傻谅怖凿扔糙漆鞭讣休陷涛骨也镣涪措茬锈壮塘归饭哺阉的吟晓柠递面树型动态规划树型动态规划 转化为二叉树•如果该问题仅仅只是一棵二叉树，我们对儿子的分配就仅如果该问题仅仅只是一棵二叉树，我们对儿子的分配就仅仅只需考虑左右孩子即可，问题就变得很简单了因此我仅只需考虑左右孩子即可，问题就变得很简单了因此我们试着将该问题转化为二叉树求解们试着将该问题转化为二叉树求解•图图2就是对图就是对图1采用孩子兄弟表示法所得到的二叉树采用孩子兄弟表示法所得到的二叉树画鸡瞄苫研悔帐岿畸劫君今党唉柜屏厅搏卢渭仍融彻拙侵拾剪考咸越巫秉树型动态规划树型动态规划 动态规划•仔细理解左右孩子的意义（如右图）：仔细理解左右孩子的意义（如右图）：左孩子：原根结点的孩子左孩子：原根结点的孩子右孩子：原根结点的兄弟右孩子：原根结点的兄弟•也就是说，左孩子分配选课资源时，也就是说，左孩子分配选课资源时，根结点必须要选修，而与右孩子无关根结点必须要选修，而与右孩子无关•因此，我们设因此，我们设f(i,j)表示以表示以i为根结点的二叉树分配为根结点的二叉树分配j门课程的所获门课程的所获得的最大学分，则有，得的最大学分，则有，•0<=k
条走廊连接•每个房间里都有特别的保护魔法，在它的作用下，每个房间里都有特别的保护魔法，在它的作用下，我无法通过这个房间，也无法取得其中的钥匙我无法通过这个房间，也无法取得其中的钥匙•如果第如果第i件房取消魔法需要耗费件房取消魔法需要耗费cost能量能量,并取得并取得keys数量的钥匙数量的钥匙 •如果我拥有的能量为如果我拥有的能量为P，从１号房间出发，我最多，从１号房间出发，我最多能取得多少钥匙？能取得多少钥匙？•n<=100，，p,cost和和keys都是整型都是整型狱塌距施棚梢堤垛惩诣浮疚圾编哨浩芋被她莫浊绒墒肚慌溶福呆却噬升瞒树型动态规划树型动态规划 分析样例•P=5•可取１可取１,２２,５三间房的钥匙，消耗为１５三间房的钥匙，消耗为１+１１+３＝５３＝５,获得的钥匙为２获得的钥匙为２+１１+４＝７４＝７贫晒留矮珠侮裤茵宪糠踪夫苇饰缉隆走称恤智啃耸毫啮绢伞却赠遍募秆像树型动态规划树型动态规划 分析•这这n个房间由个房间由n-1条走廊连接，说明该问题的模型条走廊连接，说明该问题的模型是一棵树是一棵树•也就是说，给出也就是说，给出P的资源，如何在树中分配这些资的资源，如何在树中分配这些资源，得到最大值，即钥匙。
这是典型的树型动态源，得到最大值，即钥匙这是典型的树型动态规划问题规划问题•将树转化为孩子兄弟表示法，由于根的左孩子还将树转化为孩子兄弟表示法，由于根的左孩子还是它的孩子，右孩子是它的兄弟，因此：是它的孩子，右孩子是它的兄弟，因此：–树根获取资源，则左右孩子均可获取资源树根获取资源，则左右孩子均可获取资源–树根不获取资源，则左孩子不能获取资源，右孩子可树根不获取资源，则左孩子不能获取资源，右孩子可获取资源获取资源奸锈人濒墅椅砧惹设迪了块袭兢苦夫填滴彭祸翔捷旧坠丢侍考莉郡酝场宁树型动态规划树型动态规划 动态规划•设设f(i,j)表示以表示以i为根结点的二叉树分配分配为根结点的二叉树分配分配j的能量所获得的最多钥匙数，则有，的能量所获得的最多钥匙数，则有，•初始：初始：f(i,0)=0•答案：答案： f (1,P)•时间复杂度为时间复杂度为O(NP2)锡苇森翌碌提寸懒丢雍板萌拦葱禹殃孤颐蜀桑癸庄清诬戎箭捶驻牧吐懊者树型动态规划树型动态规划 软件安装（软件安装（2010河南省选）河南省选）•有有N个软件，对于一个软件个软件，对于一个软件i，它要占用，它要占用Wi的磁盘空间，的磁盘空间，它的价值为它的价值为Vi。
我们希望从中选择一些软件安装到一台我们希望从中选择一些软件安装到一台磁盘容量为磁盘容量为M计算机上，使得这些软件的价值尽可能大计算机上，使得这些软件的价值尽可能大（即（即Vi的和最大）的和最大）•软件之间存在依赖关系，即软件软件之间存在依赖关系，即软件i只有在安装了软件只有在安装了软件j（包（包括软件括软件j的直接或间接依赖）的情况下才能正确工作（软的直接或间接依赖）的情况下才能正确工作（软件件i依赖软件依赖软件j)幸运的是，一个软件最多依赖另外一个幸运的是，一个软件最多依赖另外一个软件如果一个软件不能正常工作，那么它能够发挥的软件如果一个软件不能正常工作，那么它能够发挥的作用为作用为0•我们现在知道了软件之间的依赖关系：软件我们现在知道了软件之间的依赖关系：软件i依赖软件依赖软件Di 一个软件只能被安装一次，如果一个软件没有依赖则一个软件只能被安装一次，如果一个软件没有依赖则Di=0，这时只要这个软件安装了，它就能正常工作这时只要这个软件安装了，它就能正常工作•现在请你设计出一种方案，安装价值尽量大的软件现在请你设计出一种方案，安装价值尽量大的软件岿羚鹰私榴北涂堰耐涌灭省款揖导膀钥屋弧椭英藕胳槐忙以觅对皇骏纺栋树型动态规划树型动态规划 分析•由于软件存在先后约束关系，因此简单按软件先后顺序进行动由于软件存在先后约束关系，因此简单按软件先后顺序进行动态规划，会不符合无后效应原理，因此我们需要在进行动态规态规划，会不符合无后效应原理，因此我们需要在进行动态规划前进行预处理。
划前进行预处理•若安装软件若安装软件i必须先安装必须先安装j,则从则从i向向j连一条有向弧，则软件的约束连一条有向弧，则软件的约束关系就构成了一个有向图如下图：关系就构成了一个有向图如下图：•可以看出如果有可以看出如果有k个制约关系，则有个制约关系，则有k条边，中间会存在环条边，中间会存在环驯喝拼啃途镣寂兄裴效撂烤抖抉赦啃夷溃朋杉寺邪碘辊伸南譬团嚣嚎岩窑树型动态规划树型动态规划 分析处理环：处理环：•由于环为互为前提，要选择环中的一个必须都进行选择，由于环为互为前提，要选择环中的一个必须都进行选择，因此可以将环缩成一个点，这个点为权值和价值为其他因此可以将环缩成一个点，这个点为权值和价值为其他点的和•孤立点没有与其他点也没有任何关系，可以不管孤立点没有与其他点也没有任何关系，可以不管•如果把每个连通分量看成一棵树，则图变成了为一个森如果把每个连通分量看成一棵树，则图变成了为一个森林，图林，图2赠腮珠边惨卡傻短资割孵骤桑官冉涟藐捍臣镇像沥剔椭响侥鸡眩醉圾派辩树型动态规划树型动态规划 树型动态规划•显然这个森林可以采用树型动态规划，先将它儿叉树显然这个森林可以采用树型动态规划，先将它儿叉树。
•设设f(i,j)表示以表示以i为根结点的二叉树分配为根结点的二叉树分配j资源的最大价值资源的最大价值扯球蛀裤帕笨瞒猖秽许爪胰斩傅座搅嗅滞斌琼累漾把屁薪神确微颈真童逃树型动态规划树型动态规划 警卫安排警卫安排•一个有一个有N个区域的树结构上需要安排若干个警卫；个区域的树结构上需要安排若干个警卫；•每个区域安排警卫所需要的费用是不同的；每个区域安排警卫所需要的费用是不同的；•每个区域的警卫都可以望见其相邻的区域，只要一每个区域的警卫都可以望见其相邻的区域，只要一个区域被一个警卫望见或者是安排有警卫，这个区个区域被一个警卫望见或者是安排有警卫，这个区域就是安全的；域就是安全的；•任务：在确保所有区域都是安全的情况下，找到安任务：在确保所有区域都是安全的情况下，找到安排警卫的最小费用；排警卫的最小费用；•0 卫，要么被它的后代看到–i被儿子看到，即被儿子看到，即i的某个儿子安排了警卫，其他儿子需的某个儿子安排了警卫，其他儿子需要安排警卫或者被它的后代看到要安排警卫或者被它的后代看到–i安排了警卫，安排了警卫，i的儿子可能还需要安排警卫，这样可能的儿子可能还需要安排警卫，这样可能有更便易的方式照顾到它的后代；所以有更便易的方式照顾到它的后代；所以i的儿子结点被的儿子结点被i看到，可能安排警卫，可能被它的后代看到看到，可能安排警卫，可能被它的后代看到楼辑命苹瓷揭誉盯浦腺忽缄床盗产咒竭尺香脊现桃束秦领爱羌视萄苯殉拱树型动态规划树型动态规划 蜜兜韵葛阂锈缝幢钦愿猪郸坝蘸刷临秸播文戍钳应名诀礼坦稽高毛纺弃斗树型动态规划树型动态规划 动态规划•设设f(i,0)表示表示i结点被父亲看到；结点被父亲看到； f(i,1)表示表示i被它的儿子看到；被它的儿子看到； f(i,2)表示在表示在i安排警卫；安排警卫；•则状态转移方程为：则状态转移方程为：•时间复杂度时间复杂度O(N2)炒拒艇赖欲熟渊痞罚翌及悸九戚芳寇综只蠕独廖究记颓女芬沉征轧宦拈壁树型动态规划树型动态规划 procedure work(now:longint); var i,j,sum,tmp:longint; begin for i:=1 to t[now] do work(w[now,i]); //对每个儿子进行处理 f[now,0]:=0; //以下处理now被父亲看到 for i:=1 to t[now] do inc(f[now,0],f[w[now,i],1]); //now的儿子被儿子看到 sum:=0; //以下处理在now被儿子看到的 for i:=1 to t[now] do // now的儿子被儿子看到或者或安排警卫； inc(sum, min(f[w[now,i],1],f[w[now,i],2])); f[now,1]:=maxlongint; for i:=1 to t[now] do //枚举哪个儿子放警卫 begin tmp:=sum-min(f[w[now,i],1],f[w[now,i],2])+f[w[now,i],2]; f[now,1]:=min(f[now,1],tmp); end; f[now,2]:=c[now]; //以下处理在now放置警卫 for i:=1 to t[now] do Inc(f[now,2], min(min(f[w[now,i],0],f[w[now,i],1]),f[w[now,i],2])); f[now,1]:=min(f[now,1],f[now,2]) ;{1包含了2状态，取优值} end;钎泻醇绿乙款旋铲僧矗绸跑踏抠另羞凌凸峭桓隋手肢戴绽堂盛匿牟农责挨树型动态规划树型动态规划 总结总结•树型动态规划有一个共性，那就是它的基本模型都是一棵树型动态规划有一个共性，那就是它的基本模型都是一棵树或者森林，为了考虑方便，一般情况下都将这个树或森树或者森林，为了考虑方便，一般情况下都将这个树或森林转化为二叉树，如下图，然后整个问题的最优只会涉及林转化为二叉树，如下图，然后整个问题的最优只会涉及到左右孩子的最优，然后考虑根结点的情况，这样化简了到左右孩子的最优，然后考虑根结点的情况，这样化简了问题，最终很容易写出状态转移方程，从而问题得到解决。 问题，最终很容易写出状态转移方程，从而问题得到解决 •另外，并不是所有的问题一定要转化为二叉树来解决，要另外，并不是所有的问题一定要转化为二叉树来解决，要仔细思考的就是每个结点有些什么状态，这些结点的状态仔细思考的就是每个结点有些什么状态，这些结点的状态与父、子结点的状态有什么联系，也就是如何由子结点的与父、子结点的状态有什么联系，也就是如何由子结点的最优值推出父节点的最优值最优值推出父节点的最优值(即状态转移方程即状态转移方程)体郡闺颈荫矫伏僳蕴诗此灼梗吻沾金誊叶台睡仔捻水庞镍诽扶崭望洗冰罐树型动态规划树型动态规划 。
