nbhkdz.com冰点文库

11树型动态规划的实例分析


树型动态规划的实例分析

什么是树型动态规划
● 顾名思义,树型动态规划就是在“树”的数据结构上的动 态规划,平时作的动态规划都是线性的或者是建立在图上 的,线性的动态规划有二种方向即向前和向后,相应的线 性的动态规划有二种方法既顺推与逆推,而树型动态规划 是建立在树上的,所以也相应的有二个方向: ● 根—>叶:不过这种动态规划在实际的问题中

运用的不 多。 ● 叶->根:即根的子节点传递有用的信息给根,完后根 得出最优解的过程。这类的出现的比较多,下面就介 绍一些这类题目和它们的一般解法。

加分二叉树
● 给定一个中序遍历为1,2,3,…,n的二叉树 ● 每个结点有一个权值 ● 定义二叉树的加分规则为: ● 左子树的加分× 右子树的加分+根的分数 ● 若某个树缺少左子树或右子树,规定缺少的子树加分 为1。 ● 构造符合条件的二叉树 ● 该树加分最大 ● 输出其前序遍历序列

● 样例 ● 中序遍历为1,2,3,4,5的二叉树有很多,下图是其 中的三棵,其中第三棵加分最大,为145.

分析
● 性质:中序遍历是按“左-根-右”方式进行遍历二叉树, 因此二叉树左孩子遍历序列一定在根结点的左边,右孩子 遍历序列一定在根结点的右边! ● 因此,假设二叉树的根结点为k,那么中序遍历为1,2,…,n 的遍历序列,左孩子序列为1,2,…,k-1,右孩子序列为 k+1,k+2,…,n,如下图

选课
● [问题描述] ● 在大学里每个学生,为了达到一定的学分,必须从很多课 程里选择一些课程来学习,在课程里有些课程必须在某些 课程之前学习,如高等数学总是在其它课程之前学习。 ● 现在有N门功课,每门课有个学分,每门课有一门或没有 直接先修课(若课程a是课程b的先修课即只有学完了课程 a,才能学习课程b)。 ● 一个学生要从这些课程里选择M门课程学习,问他能获得 的最大学分是多少?

● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

输入: 第一行有两个整数N,M用空格隔开。(1<=N<=200,1<=M<=150) 接下来的N行,第I+1行包含两个整数ki和si, ki表示第I门课的直接先修课,si表示第I门课 的学分。若ki=0表示没有直接先修课(1<=ki<=N, 1<=si<=20)。 输出: 只有一行,选M门课程的最大得分。 样例: 输入: 7 4 2 2 0 1 0 4 2 1 7 1 7 6 2 2 输出: 13

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

样例分析
● 如图1,为两棵树,我们可以虚拟一个结点,将这 些树连接起来,那么森林就转会为了1棵树,选取 结点时,从每个儿子出发进行选取。显然选M=4 时,选3,2,7,6几门课程最优。

转化为二叉树
? 如果该问题仅仅只是一棵二叉树,我们对儿子的分配就仅 仅只需考虑左右孩子即可,问题就变得很简单了。因此我 们试着将该问题转化为二叉树求解。

? 图2就是对图1采用孩子兄弟表示法所得到的二叉树

建立二叉树
● 边读数据边把二叉树建立第一个孩子作为父节点的左子树,其它孩子作为第 一个孩子的右子树。 ● type ● tree=record ● l,r,v:longint; ● end; ● f:array[0..200] of longint; ● a:array[0..200] of tree; ● for i:=1 to n do ● begin ● readln(k,s); ● a[i].v:=s; ● if f[k]=0 then a[k].l:=i ● else a[f[k]].r:=i; ● f[k]:=i; ● end;

动态规划
● 仔细理解左右孩子的意义(如右图): 左孩子:原根结点的孩子 右孩子:原根结点的兄弟 ● 也就是说,左孩子分配选课资源时, 根结点必须要选修,而与右孩子无关。

? f (il , k ) ? f (ir , j ? k ? 1) ? a[i], 根结点选修 f (i, j ) ? max? ? f (ir , j), 根结点不选修

? ? ?

?

? ●

样例求解过程:初始f(i,0)=0 f(6,1)=6, f(5,1)=max{1,6}=6, f(7,1)=2 f(4,1)=max{1,2}=2, f(1,1)=max{1,f(4,1)}=2 f(3,1)=4, f(2,1)=max{1,4}=4 f(5,2)=7 f(7,2)=max{f(5,1)+2}=8 f(4,2)=max{f(7,2),f(7,1)+1}=8 f(1,2)=max{f(4,2),f(4,1)+2}=8 f(2,2)=max{f(1,1)+1, f(3,1)+1)}=5 f(7,3)=9 f(4,3)=max{f(7,2)+1,f(7,3)}=9 f(1,3)=max{f(4,2)+1,f(4,3)}=9 f(2,3)=max{f(1,1)+f(3,1)+1,f(1,2)+1}=9 f(2,4)=max{f(1,3)+1, f(1,2)+f(3,1)+1}=max{9+1,8+4+1}=13 因此,我们设f(i,j)表示以i为根结点的二叉树分配j门课程的所获得的最大学 分,则有,

● 0<=k<j<n, i ∈(1..m) ● 时间复杂度O(mn2)

? f (il , k ? 1) ? f (ir , j ? k ) ? a[i], 根结点选修 f (i, j ) ? max? ? f (ir , j), 根结点不选修

递归实现树型DP
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● procedure treedp(x,y:longint); var i,j,k,l:longint; begin if b[x,y]>=0 then exit; treedp(a[x].r,y);{只有右子树的情况} j:=b[a[x].r,y]; for k:=1 to y do{左右子树都有的情况} begin treedp(a[x].l,k-1); treedp(a[x].r,y-k); i:=b[a[x].l,k-1]+b[a[x].r,y-k]+a[x].k; if i>j then j:=i; end; b[x,y]:=j; end;


动态规划100例

81 树形动态规划 11(完全二叉树) NOI2006 网络收费 ... 83 树形动态...下 表就是一些主件与附件的例子: 主件 附件 电脑 打印机,扫描仪 书柜 图书 书桌 ...

动态规划总结

动态规划例题总结 11页 2下载券 树形动态规划总结 15页 免费 动态规划阶段总结...1.1. 编号(长度)动态规划共性总结 本类的状态是基础的基础,大部分的动态规划...

动态规划

主持人还举了如下的一个例子: 有一个数字串:312...树型动态规划 2 ---选课 (多叉树转二叉树,自顶...11 0 6 5 0 Sample Output 25 56 组合数: ...

0020算法笔记——【动态规划】最优二叉搜索树问题

5、复杂度分析与优化: 算法中用到 3 个数组 m,s 和 w,故所需空间复杂度...//3d11-1 最优二叉搜索树 动态规划加速原理 四边形不等式 2. #include "...

※动态规划经典教程

多进程动态规划 例题 28 方格取数 4.树型动态规划 例题 29 加分二叉树例题 ...下面看个例子: 例题 11 Money Systems (money.pas/c/cpp) 来源:USACO 2.3...

二叉苹果树(树形动规)解题报告

这两个 问题用树型动态规划来做的话都是 O(n)的。 例:二叉苹果树 问题...文档贡献者 y403899457 贡献于2010-11-16 1/2 相关文档推荐 苹果树采用什么...

动态规划_状态转移方程

负正 f[I,k]*g[k+1,j];} g 为 min 11....? ? 50 树形动态规划 树形动态规划 ---聚会的快乐...d[i,j]=d[j,i],所以我们限制 i>j , 分析...

树形动规

只要你掌握了动态规划的思想, 将它应用在树形结构里面...举个简单的例子,如图一所示1: 1 2 3 将整个二叉...文档贡献者 415137850 贡献于2011-11-04 ...

动态规划动态转移方程大全

负正 f[I,k]*g[k+1,j];} g 为 min 11....[I,0]:=1 57 树形动态规划 ---有向树 k 中值...动态规划的应用举例大全 暂无评价 16页 免费 传送网...

★经典动态规划收集

树型动态规划 11.树型动态规划 1 ---加分二叉树 (从两侧到根结点模型) F[I,j]:=max{f[I,k-1]*f[k+1,j]+c[k]} 12.树型动态规划 12.树型动态...