《朱全民树型动态规划》由会员分享，可在线阅读，更多相关《朱全民树型动态规划（24页珍藏版）》请在金锄头文库上搜索。
1、树型动态规划树型动态规划加分二叉树加分二叉树给定一个中序遍历为给定一个中序遍历为1,2,3,n1,2,3,n的二叉树的二叉树每个结点有一个权值每个结点有一个权值定义二叉树的加分规则为：定义二叉树的加分规则为：左子树的加分左子树的加分 右子树的加分根的分数右子树的加分根的分数若某个树缺少左子树或右子树，规定缺少的子若某个树缺少左子树或右子树，规定缺少的子树加分为树加分为1 1。构造符合条件的二叉树构造符合条件的二叉树该树加分最大该树加分最大输出其前序遍历序列输出其前序遍历序列样例样例中序遍历为中序遍历为1,2,3,4,51,2,3,4,5的二叉树有很多，下的二叉树有很多，下图是其中的三棵，其中第
2、三棵加分最大，图是其中的三棵，其中第三棵加分最大，为为145.145.分析性质：中序遍历是按性质：中序遍历是按“左左- -根根- -右右”方式进行遍历二叉树，方式进行遍历二叉树，因此二叉树左孩子遍历序列一定在根结点的左边，右孩子因此二叉树左孩子遍历序列一定在根结点的左边，右孩子遍历序列一定在根结点的右边！遍历序列一定在根结点的右边！因此，假设二叉树的根结点为因此，假设二叉树的根结点为k k，那么中序遍历为，那么中序遍历为1,2,n1,2,n的遍历序列，左孩子序列为的遍历序列，左孩子序列为1,2,k-11,2,k-1，右孩子，右孩子序列为序列为k+1,k+2,nk+1,k+2,n，如下图，如下图
3、动态规划设设f(i,j)f(i,j)中序遍历为中序遍历为i,i+1,ji,i+1,j的二叉树的最大加的二叉树的最大加分，则有：分，则有： f(i,j)=maxfi,k-1*fk+1,j +dkf(i,j)=maxfi,k-1*fk+1,j +dk显然显然 f(i,i)=dif(i,i)=di答案为答案为f(1,n)f(1,n)1=i=k=j=n1=i=k=j=n时间复杂度时间复杂度 O(nO(n3 3) )要构造这个树，只需记录每次的决策值，令要构造这个树，只需记录每次的决策值，令b(i,j)=kb(i,j)=k，表示中序遍历为，表示中序遍历为i,i+1,ji,i+1,j的二叉树的的二叉树的取
4、最优决策时的根结点为取最优决策时的根结点为k k最后前序遍历这个树即可。最后前序遍历这个树即可。选课选课给定给定M M门课程，每门课程有一个学分门课程，每门课程有一个学分要从要从M M门课程中选择门课程中选择N N门课程，使得学分总门课程，使得学分总和最大和最大其中选择课程必须满足以下条件：其中选择课程必须满足以下条件：每门课程最多只有一门直接先修课每门课程最多只有一门直接先修课要选择某门课程，必须先选修它的先修课要选择某门课程，必须先选修它的先修课M,N=500M,N=500分析每门课程最多只有每门课程最多只有1 1门直接先修课，如果我们把课门直接先修课，如果我们把课程看成结点，也就是说每个
5、结点最多只一个前驱程看成结点，也就是说每个结点最多只一个前驱结点。结点。如果把前驱结点看成父结点，换句话说，每个结如果把前驱结点看成父结点，换句话说，每个结点只有一个父结点。显然具有这种结构的模型是点只有一个父结点。显然具有这种结构的模型是树结构，要么是一棵树，要么是一个森林。树结构，要么是一棵树，要么是一个森林。这样，问题就转化为在一个这样，问题就转化为在一个M M个结点的森林中选取个结点的森林中选取N N个结点，使得所选结点的权值之和最大。同时满个结点，使得所选结点的权值之和最大。同时满足每次选取时，若选儿子结点，必选根结点的条足每次选取时，若选儿子结点，必选根结点的条件。件。样例分析如图
6、如图1 1，为两棵树，我们可以虚拟一个结点，将这，为两棵树，我们可以虚拟一个结点，将这些树连接起来，那么森林就转会为了些树连接起来，那么森林就转会为了1 1棵树，选取棵树，选取结点时，从每个儿子出发进行选取。显然选结点时，从每个儿子出发进行选取。显然选M=4M=4时，时，选选3 3，2 2，7 7，6 6几门课程最优。几门课程最优。转化为二叉树如果该问题仅仅只是一棵二叉树，我们对儿子的分配就仅如果该问题仅仅只是一棵二叉树，我们对儿子的分配就仅仅只需考虑左右孩子即可，问题就变得很简单了。因此我仅只需考虑左右孩子即可，问题就变得很简单了。因此我们试着将该问题转化为二叉树求解。们试着将该问题转化为二
7、叉树求解。图图2 2就是对图就是对图1 1采用孩子兄弟表示法所得到的二叉树采用孩子兄弟表示法所得到的二叉树动态规划仔细理解左右孩子的意义（如右图）：仔细理解左右孩子的意义（如右图）：左孩子：原根结点的孩子左孩子：原根结点的孩子右孩子：原根结点的兄弟右孩子：原根结点的兄弟也就是说，左孩子分配选课资源时，也就是说，左孩子分配选课资源时，根结点必须要选修，而与右孩子无关。根结点必须要选修，而与右孩子无关。因此，我们设因此，我们设f(i,j)f(i,j)表示以表示以i i为根结点的二叉树分配为根结点的二叉树分配j j门课程的门课程的所获得的最大学分，则有，所获得的最大学分，则有，0=kjn, i (1
8、.m)0=kj n m; fin n m; scoren+1 = 0; scoren+1 = 0; brothern+1 = 0; brothern+1 = 0; / / 输入数据并转化为左儿子右兄弟表示法输入数据并转化为左儿子右兄弟表示法 for (int i=1; i=n; +i) for (int i=1; i a b; fin a b; if (a = 0) a = n + 1; if (a = 0) a = n + 1; scorei = b; scorei = b; brotheri = childa; brotheri = childa; childa = i; childa =
9、 i; void dfs( int i, int j)void dfs( int i, int j) if (visitedij) return; if (visitedij) return; visitedij = 1; visitedij = 1; if (i=0 | j=0) return; if (i=0 | j=0) return; dfs(brotheri, j); / dfs(brotheri, j); / 如果不选如果不选i i，则转移到状态，则转移到状态(brotheri, j)(brotheri, j) fij = fbrotherij; fij = fbrotherij;
10、 for (int k=0; kj; +k) for (int k=0; k fij) scorei fij) fij = fbrotherik + fchildij-k- fij = fbrotherik + fchildij-k-1 + scorei;1 + scorei; 软件安装软件安装（20102010河南省选）河南省选）有有N N个软件，对于一个软件个软件，对于一个软件i i，它要占用，它要占用W Wi i的磁盘空间，的磁盘空间，它的价值为它的价值为V Vi i。我们希望从中选择一些软件安装到一台。我们希望从中选择一些软件安装到一台磁盘容量为磁盘容量为M M计算机上，使得这些软件的
11、价值尽可能大计算机上，使得这些软件的价值尽可能大（即（即V Vi i的和最大）。的和最大）。软件之间存在依赖关系，即软件软件之间存在依赖关系，即软件i i只有在安装了软件只有在安装了软件j j（包括软件（包括软件j j的直接或间接依赖）的情况下才能正确工作的直接或间接依赖）的情况下才能正确工作（软件（软件i i依赖软件依赖软件j)j)。幸运的是，一个软件最多依赖另外。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为挥的作用为0 0。我们现在知道了软件之间的依赖关系：软件我们现在知道了软件之间的依赖关系：软件
12、i i依赖软件依赖软件D Di i。 一个软件只能被安装一次，如果一个软件没有依赖则一个软件只能被安装一次，如果一个软件没有依赖则D Di i=0=0，这时只要这个软件安装了，它就能正常工作。，这时只要这个软件安装了，它就能正常工作。现在请你设计出一种方案，安装价值尽量大的软件。现在请你设计出一种方案，安装价值尽量大的软件。分析由于软件存在先后约束关系，因此简单按软件先后顺序进行动由于软件存在先后约束关系，因此简单按软件先后顺序进行动态规划，会不符合无后效应原理，因此我们需要在进行动态规态规划，会不符合无后效应原理，因此我们需要在进行动态规划前进行预处理。划前进行预处理。若安装软件若安装软件i
13、 i必须先安装必须先安装j,j,则从则从i i向向j j连一条有向弧，则软件的约连一条有向弧，则软件的约束关系就构成了一个有向图。如下图：束关系就构成了一个有向图。如下图：可以看出如果有可以看出如果有k k个制约关系，则有个制约关系，则有k k条边，中间会存在环条边，中间会存在环分析处理环：处理环：由于环为互为前提，要选择环中的一个必须都进行选择，由于环为互为前提，要选择环中的一个必须都进行选择，因此可以将环缩成一个点，这个点为权值和价值为其他因此可以将环缩成一个点，这个点为权值和价值为其他点的和。点的和。孤立点没有与其他点也没有任何关系，可以不管。孤立点没有与其他点也没有任何关系，可以不管。
14、如果把每个连通分量看成一棵树，则图变成了为一个森如果把每个连通分量看成一棵树，则图变成了为一个森林，图林，图2 2。树型动态规划显然这个森林可以采用树型动态规划，先将它儿叉树。显然这个森林可以采用树型动态规划，先将它儿叉树。设设f(i,j)f(i,j)表示以表示以i i为根结点的二叉树分配为根结点的二叉树分配j j资源的最大价值资源的最大价值警卫安排警卫安排一个有一个有N N个区域的树结构上需要安排若干个警卫；个区域的树结构上需要安排若干个警卫；每个区域安排警卫所需要的费用是不同的；每个区域安排警卫所需要的费用是不同的；每个区域的警卫都可以望见其相邻的区域，只要一每个区域的警卫都可以望见其相邻
15、的区域，只要一个区域被一个警卫望见或者是安排有警卫，这个区个区域被一个警卫望见或者是安排有警卫，这个区域就是安全的；域就是安全的；任务：在确保所有区域都是安全的情况下，找到安任务：在确保所有区域都是安全的情况下，找到安排警卫的最小费用；排警卫的最小费用；0n=720；分析样例分析样例该图有该图有6 6个区域如图个区域如图1 1，安排情况如图，安排情况如图2 2，红色点为安排，红色点为安排了警卫。了警卫。2 2号警卫可以观察号警卫可以观察1 1，2 2，5 5，6 6；3 3号警卫可以观察号警卫可以观察1 1，3 3； 4 4号警卫可以观察号警卫可以观察1 1，4 4；费用：费用：16+5+4=
16、2516+5+4=25分析对于每个点对于每个点i i，都有，都有3 3种状态分别为：种状态分别为：要么在父亲结点安排警卫，即被父亲看到要么在父亲结点安排警卫，即被父亲看到要么在儿子结点安排警卫，即被儿子看到要么在儿子结点安排警卫，即被儿子看到要么安排警卫要么安排警卫对于对于i ii i被父亲看到，这时被父亲看到，这时i i没有安排警卫，没有安排警卫，i i的儿子要么安排的儿子要么安排警卫，要么被它的后代看到。警卫，要么被它的后代看到。i i被儿子看到，即被儿子看到，即i i的某个儿子安排了警卫，其他儿子需的某个儿子安排了警卫，其他儿子需要安排警卫或者被它的后代看到。要安排警卫或者被它的后代看到
17、。i i安排了警卫，安排了警卫，i i的儿子可能还需要安排警卫，这样可能的儿子可能还需要安排警卫，这样可能有更便易的方式照顾到它的后代；所以有更便易的方式照顾到它的后代；所以i i的儿子结点被的儿子结点被i i看到，可能安排警卫，可能被它的后代看到。看到，可能安排警卫，可能被它的后代看到。动态规划设设f(i,0)f(i,0)表示表示i i结点被父亲看到；结点被父亲看到； f(i,1) f(i,1)表示表示i i被它的儿子看到；被它的儿子看到； f(i,2) f(i,2)表示在表示在i i安排警卫；安排警卫；则状态转移方程为：则状态转移方程为：时间复杂度时间复杂度O(NO(N2 2) )proc
18、edure 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); fnow,1:=maxlongint;
19、 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;总结总结树型动态规划有一个共性，那就是它的基本模型都是一棵树型动态规划有一个共性，那
20、就是它的基本模型都是一棵树或者森林，为了考虑方便，一般情况下都将这个树或森树或者森林，为了考虑方便，一般情况下都将这个树或森林转化为二叉树，如下图，然后整个问题的最优只会涉及林转化为二叉树，如下图，然后整个问题的最优只会涉及到左右孩子的最优，然后考虑根结点的情况，这样化简了到左右孩子的最优，然后考虑根结点的情况，这样化简了问题，最终很容易写出状态转移方程，从而问题得到解决。问题，最终很容易写出状态转移方程，从而问题得到解决。 另外，并不是所有的问题一定要转化为二叉树来解决，要另外，并不是所有的问题一定要转化为二叉树来解决，要仔细思考的就是每个结点有些什么状态，这些结点的状态仔细思考的就是每个结点有些什么状态，这些结点的状态与父、子结点的状态有什么联系，也就是如何由子结点的与父、子结点的状态有什么联系，也就是如何由子结点的最优值推出父节点的最优值最优值推出父节点的最优值( (即状态转移方程即状态转移方程) )。
