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;


树型动态规划的实例分析(完美整理)

树型动态规划的实例分析(完美整理)_计算机软件及应用_IT/计算机_专业资料。树型动态规划的实例分析的完美整理版哈树型动态规划的实例分析中山市华侨中学——李彦亭 ...

树型动态规划 tree dp

11树型动态规划的实例分析 14页 2财富值 10 树型动态规划 13页 免费喜欢此文档的还喜欢 树形DP之个人整理总结 41页 2财富值 树形DP 11页 免费 树型dp 11页...

树型动态规划

treeDP 树型动态规划 什么是树型动态规划 顾名思义,树型动态规划就是在“树...[输出样例 输出样例] 输出样例 23 241 1 11 1 3 16 1 [数据范围 数据...

树形动态规划

11页 免费 树形DP之个人整理总结 41页 2财富值 树形动态规划讲解 37页 5财富...【问题描述】 设一个 n 个节点的二叉树 tree 的中序遍历为 (l,2,3,…,...

动态规划算法举例分析

动态规划算法举例分析_数学_自然科学_专业资料。动态规划算法 1. 动态规划算法介绍...若设 x1 = 0,则对于剩下的两种物品而言,容量限制 条件为 11 6。总之,如果...

动态规划讲解大全(含例题及答案)

动态规划讲解大全(含例题及答案)_IT认证_资格考试/...让我们通过对前面的例子分析来具体说明这一点:从...SAMPLE OUTPUT (file game1.out) 18 11 参考程序...

树的动态规划与构造

本文通过几道关于树的题目, 分析树的动态规划与...下面举一些例子谈谈树的动态规划与构造。 一、树的...Problem Set 149 (acm.sgu.ru) Input 3 11 12 ...

动态规划总结

动态规划例题总结 11页 2下载券 树形动态规划总结 15页 免费 动态规划阶段总结...5.树型动态规划共性总结 1) 动态规划的顺序 一般按照后序遍历的顺序,即处理完...

深入分析区间型动态规划

二、区间型动态规划的算法分析 在这里就以经典的最小代价字母树作为例子,对区间...文档贡献者 neoloong 贡献于2010-11-16 1/2 相关文档推荐 NOI导刊 区间类型...