NOI导刊树型动态规划.ppt

《NOI导刊树型动态规划.ppt》由会员分享，可在线阅读，更多相关《NOI导刊树型动态规划.ppt（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、树型动态规划树型动态规划长沙市雅礼中学长沙市雅礼中学 朱全民朱全民加分二叉加分二叉树给定一个中序遍定一个中序遍历为1,2,3,n的二叉的二叉树每个每个结点有一个点有一个权值定定义二叉二叉树的加分的加分规则为：左子左子树的加分的加分 右子右子树的加分根的分数的加分根的分数若某个若某个树缺少左子缺少左子树或右子或右子树，规定缺少的子定缺少的子树加分加分为1。构造符合条件的二叉构造符合条件的二叉树该树加分最大加分最大输出其前序遍出其前序遍历序列序列样例例中序遍中序遍历为1,2,3,4,5的二叉的二叉树有很多，下有很多，下图是其中的三棵，其中第三棵加分最大，是其中的三棵，其中第三棵加分最大，为145.

2、分析性性质：中序遍：中序遍历是按是按“左左-根根-右右”方式方式进行遍行遍历二叉二叉树，因，因此二叉此二叉树左孩子遍左孩子遍历序列一定在根序列一定在根结点的左点的左边，右孩子遍，右孩子遍历序列一定在根序列一定在根结点的右点的右边！因此，假因此，假设二叉二叉树的根的根结点点为k，那么中序遍，那么中序遍历为1,2,n的遍的遍历序列，左孩子序列序列，左孩子序列为1,2,k-1，右孩子序列，右孩子序列为k+1,k+2,n，如下，如下图动态规划设f(i,j)中序遍中序遍历为i,i+1,j的二叉的二叉树的最大加分，的最大加分，则有：有：f(i,j)=maxfi,k-1*fk+1,j+dk显然然 f(i,i

3、)=di答案答案为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分析

4、每每门课程最多只有程最多只有1门直接先修直接先修课，如果我，如果我们把把课程看成程看成结点，也就是点，也就是说每个每个结点最多只一个前点最多只一个前驱结点。点。如果把前如果把前驱结点看成父点看成父结点，点，换句句话说，每个，每个结点只有一个父点只有一个父结点。点。显然具有然具有这种种结构的模型是构的模型是树结构，要么是一棵构，要么是一棵树，要么是一个森林。，要么是一个森林。这样，问题就就转化化为在一个在一个M个个结点的森林中点的森林中选取取N个个结点，使得所点，使得所选结点的点的权值之和最大。同之和最大。同时满足每次足每次选取取时，若，若选儿子儿子结点，必点，必选根根结点的点的条件。条件。样例

5、分析如如图1，为两棵两棵树，我，我们可以虚可以虚拟一个一个结点，将点，将这些些树连接起来，那么森林就接起来，那么森林就转会会为了了1棵棵树，选取取结点点时，从每个儿子出，从每个儿子出发进行行选取。取。显然然选M=4时，选3，2，7，6几几门课程最程最优。转化为二叉树如果如果该问题仅仅只是一棵二叉只是一棵二叉树，我，我们对儿子的分配就儿子的分配就仅仅只需考只需考虑左右孩子即可，左右孩子即可，问题就就变得很得很简单了。因此我了。因此我们试着将着将该问题转化化为二叉二叉树求解。求解。图2就是就是对图1采用孩子兄弟表示法所得到的二叉采用孩子兄弟表示法所得到的二叉树动态规划仔仔细理解左右孩子的意理解左右

6、孩子的意义（如右（如右图）：）：左孩子：原根左孩子：原根结点的孩子点的孩子右孩子：原根右孩子：原根结点的兄弟点的兄弟也就是也就是说，左孩子分配，左孩子分配选课资源源时，根根结点必点必须要要选修，而与右孩子无关。修，而与右孩子无关。因此，我因此，我们设f(i,j)表示以表示以i为根根结点的二叉点的二叉树分配分配j门课程的所程的所获得的最大学分，得的最大学分，则有，有，0=kj n m;scoren+1=0;brothern+1=0;/输入数据并入数据并转化化为左儿子右兄弟表示法左儿子右兄弟表示法 for(int i=1;i a b;if(a=0)a=n+1;scorei=b;brotheri=c

7、hilda;childa=i;void dfs(int i,int j)if(visitedij)return;visitedij=1;if(i=0|j=0)return;dfs(brotheri,j);/如果不如果不选i，则转移到状移到状态(brotheri,j)fij=fbrotherij;for(int k=0;k fij)fij=fbrotherik+fchildij-k-1+scorei;软软件安装件安装（2010河南省河南省选）有有N个个软软件，件，对对于一个于一个软软件件i，它要占用，它要占用Wi的磁的磁盘盘空空间间，它的价它的价值为值为Vi。我。我们们希望从中希望从中选择选择一

8、些一些软软件安装到一台件安装到一台磁磁盘盘容量容量为为M计计算机上，使得算机上，使得这这些些软软件的价件的价值值尽可能大尽可能大（即（即Vi的和最大）。的和最大）。软软件之件之间间存在依存在依赖赖关系，即关系，即软软件件i只有在安装了只有在安装了软软件件j（包（包括括软软件件j的直接或的直接或间间接依接依赖赖）的情况下才能正确工作（）的情况下才能正确工作（软软件件i依依赖软赖软件件j)。幸运的是，一个。幸运的是，一个软软件最多依件最多依赖赖另外一个另外一个软软件。如果一个件。如果一个软软件不能正常工作，那么它能件不能正常工作，那么它能够发挥够发挥的的作用作用为为0。我我们现们现在知道了在知道了

9、软软件之件之间间的依的依赖赖关系：关系：软软件件i依依赖软赖软件件Di。一个一个软软件只能被安装一次，如果一个件只能被安装一次，如果一个软软件没有依件没有依赖则赖则Di=0，这时这时只要只要这这个个软软件安装了，它就能正常工作。件安装了，它就能正常工作。现现在在请请你你设计设计出一种方案，安装价出一种方案，安装价值值尽量大的尽量大的软软件。件。分析由于由于软件存在先后件存在先后约束关系，因此束关系，因此简单按按软件先后件先后顺序序进行行动态规划，会不符合无后效划，会不符合无后效应原理，因此我原理，因此我们需要在需要在进行行动态规划前划前进行行预处理。理。若安装若安装软件件i必必须先安装先安装j

10、,则从从i向向j连一条有向弧，一条有向弧，则软件的件的约束束关系就构成了一个有向关系就构成了一个有向图。如下。如下图：可以看出如果有可以看出如果有k个制个制约关系，关系，则有有k条条边，中，中间会存在会存在环分析处理理环：由于由于环为互互为前提，要前提，要选择环中的一个必中的一个必须都都进行行选择，因此可以将因此可以将环缩成一个点，成一个点，这个点个点为权值和价和价值为其他其他点的和。点的和。孤立点没有与其他点也没有任何关系，可以不管。孤立点没有与其他点也没有任何关系，可以不管。如果把每个如果把每个连通分量看成一棵通分量看成一棵树，则图变成了成了为一个森一个森林，林，图2。树型动态规划显然然这

11、个森林可以采用个森林可以采用树型型动态规划，先将它儿叉划，先将它儿叉树。设f(i,j)表示以表示以i为根根结点的二叉点的二叉树分配分配j资源的最大价源的最大价值警警卫安排安排一个有一个有N个区域的个区域的树结构上需要安排若干个警构上需要安排若干个警卫；每个区域安排警每个区域安排警卫所需要的所需要的费用是不同的；用是不同的；每个区域的警每个区域的警卫都可以望都可以望见其相其相邻的区域，只要一的区域，只要一个区域被一个警个区域被一个警卫望望见或者是安排有警或者是安排有警卫，这个区个区域就是安全的；域就是安全的；任任务：在确保所有区域都是安全的情况下，找到安：在确保所有区域都是安全的情况下，找到安排

12、警排警卫的最小的最小费用；用；0n=720；分析分析样例例该图有有6个区域如个区域如图1，安排情况如，安排情况如图2，红色点色点为安排安排了警了警卫。2号警号警卫可以可以观察察1，2，5，6；3号警号警卫可以可以观察察1，3；4号警号警卫可以可以观察察1，4；费用：用：16+5+4=25分析对于每个点于每个点i，都有，都有3种状种状态分分别为：要么在父要么在父亲结点安排警点安排警卫，即被父，即被父亲看到看到要么在儿子要么在儿子结点安排警点安排警卫，即被儿子看到，即被儿子看到要么安排警要么安排警卫对于于ii被父被父亲看到，看到，这时i没有安排警没有安排警卫，i的儿子要么安排警的儿子要么安排警卫，

13、要么被它的后代看到。，要么被它的后代看到。i被儿子看到，即被儿子看到，即i的某个儿子安排了警的某个儿子安排了警卫，其他儿子需，其他儿子需要安排警要安排警卫或者被它的后代看到。或者被它的后代看到。i安排了警安排了警卫，i的儿子可能的儿子可能还需要安排警需要安排警卫，这样可能可能有更便易的方式照有更便易的方式照顾到它的后代；所以到它的后代；所以i的儿子的儿子结点被点被i看到，可能安排警看到，可能安排警卫，可能被它的后代看到。，可能被它的后代看到。动态规划设f(i,0)表示表示i结点被父点被父亲看到；看到；f(i,1)表示表示i被它的儿子看到；被它的儿子看到；f(i,2)表示在表示在i安排警安排警卫

14、；则状状态转移方程移方程为：时间复复杂度度O(N2)procedure work(now:longint);var i,j,sum,tmp:longint;begin for i:=1 to tnow do work(wnow,i);/对每个儿子进行处理 fnow,0:=0;/以下处理now被父亲看到 for i:=1 to tnow do inc(fnow,0,fwnow,i,1);/now的儿子被儿子看到sum:=0;/以下处理在now被儿子看到的 for i:=1 to tnow do /now的儿子被儿子看到或者或安排警卫；inc(sum,min(fwnow,i,1,fwnow,i,2

15、);fnow,1:=maxlongint;for i:=1 to tnow do/枚举哪个儿子放警卫 begin tmp:=sum-min(fwnow,i,1,fwnow,i,2)+fwnow,i,2;fnow,1:=min(fnow,1,tmp);end;fnow,2:=cnow;/以下处理在now放置警卫 for i:=1 to tnow do Inc(fnow,2,min(min(fwnow,i,0,fwnow,i,1),fwnow,i,2);fnow,1:=min(fnow,1,fnow,2);1包含了2状态，取优值 end;总结树型型动态规划有一个共性，那就是它的基本模型都是一棵划有

16、一个共性，那就是它的基本模型都是一棵树或者森林，或者森林，为了考了考虑方便，一般情况下都将方便，一般情况下都将这个个树或森或森林林转化化为二叉二叉树，如下，如下图，然后整个，然后整个问题的最的最优只会涉及只会涉及到左右孩子的最到左右孩子的最优，然后考，然后考虑根根结点的情况，点的情况，这样化化简了了问题，最，最终很容易写出状很容易写出状态转移方程，从而移方程，从而问题得到解决。得到解决。另外，并不是所有的另外，并不是所有的问题一定要一定要转化化为二叉二叉树来解决，要来解决，要仔仔细思考的就是每个思考的就是每个结点有些什么状点有些什么状态，这些些结点的状点的状态与父、子与父、子结点的状点的状态有什么有什么联系，也就是如何由子系，也就是如何由子结点的点的最最优值推出父推出父节点的最点的最优值(即状即状态转移方程移方程)。