《《树型动态规划》PPT课件》由会员分享，可在线阅读，更多相关《《树型动态规划》PPT课件（15页珍藏版）》请在金锄头文库上搜索。
1、树型动态规划朱全民加分二叉树加分二叉树 设一个设一个n个节点的二叉树个节点的二叉树tree的中序遍历为（的中序遍历为（l,2,3,n），），其中数字其中数字1,2,3,n为节点编号。每个节点都有一个分数（均为节点编号。每个节点都有一个分数（均为正整数），记第为正整数），记第j个节点的分数为个节点的分数为di，tree及它的每个子树及它的每个子树都有一个加分，任一棵子树都有一个加分，任一棵子树subtree（也包含（也包含tree本身）的加本身）的加分计算方法如下：分计算方法如下： subtree的左子树的加分的左子树的加分 subtree的右子树的加分的右子树的加分subtree的根的分数的根
2、的分数若某个子树为主，规定其加分为若某个子树为主，规定其加分为1，叶子的加分就是叶节点，叶子的加分就是叶节点本身的分数。不考虑它的空。本身的分数。不考虑它的空。子树。子树。试求一棵符合中序遍历为（试求一棵符合中序遍历为（1,2,3,n）且加分最高的二叉树）且加分最高的二叉树tree。要求输出；。要求输出； （1）tree的最高加分的最高加分 （2）tree的前序遍历的前序遍历例一例一 加分二叉树加分二叉树【输入格式】【输入格式】 第第1行：一个整数行：一个整数n（n30），为节点个数。），为节点个数。 第第2行：行：n个用空格隔开的整数，为每个节点的分数（分数个用空格隔开的整数，为每个节点的分
3、数（分数100）。）。【输出格式】【输出格式】 第第1行：一个整数，为最高加分（结果不会超过行：一个整数，为最高加分（结果不会超过4,000,000,000）。）。 第第2行：行：n个用空格隔开的整数，为该树的前序遍历。个用空格隔开的整数，为该树的前序遍历。【输入样例】【输入样例】 5 5 7 1 2 10【输出样例】【输出样例】 145 3 1 2 4 5分析如果整棵树的权值最大，必然有左子树的权值最大，右子树德权值也最大，符合最优性原理。可行算法可行算法我们试着写出状态转移方程：我们试着写出状态转移方程：fi,j=maxi=t=j | dt+fi,t-1ft+1,j 初始：初始： f(i,
4、i)=di 目标：目标：f(1,n)这样，我们可以写出一个动态规划的算法，可以按照这样，我们可以写出一个动态规划的算法，可以按照状态状态fi,j中中i与与j的距离来划分阶段的距离来划分阶段(当然也有其它的划当然也有其它的划分阶段的办法分阶段的办法),先处理掉边界情况先处理掉边界情况(空树和只含有一个空树和只含有一个节点的树节点的树),然后就可以按照阶段自底向上进行动态规然后就可以按照阶段自底向上进行动态规划了，最后再递归地输出，注意要保存每次决策。划了，最后再递归地输出，注意要保存每次决策。时间复杂度时间复杂度 O(n3)例二 选课 大学里实行学分。每门课程都有一定的学分，学生只要选修了这门课
5、并考核通过就能获得相应的学分。学生最后的学分是他选修的各门课的学分的总和。每个学生都要选择规定数量的课程。其中有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。例如，数据结构必须在选修了高级语言程序设计之后才能选修。我们称高级语言程序设计是数据结构的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。为便于表述每门课都有一个课号，课号依次为1，2，3，。 选课下面举例说明上例中1是2的先修课，即如果要选修2，则1必定已被选过。同样，如果要选修3，那么1和2都一定已被选修过。学生不可能学完大学所开设的所有课程，因此必须在入学时选定自己要
6、学的课程。每个学生可选课程的总数是给定的。现在请你找出一种选课方案，使得你能得到学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。选课 输入输入 输入文件的第一行包括两个正整数M、N（中间用一个空格隔开）其中M表示待选课程总数（1M1000)，N表示学生可以选的课程总数（1NM)。 以下M行每行代表一门课，课号依次为1，2M。每行有两个数（用一个空格隔开），第一个数为这门课的先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。学分是不超过10的正整数。输出输出 输出文件第一行只有一个数，即实际所选课程的学分总数。以下N行每行有一个数，表示学生所选课程的课号。
7、样例分析7 42 20 10 42 17 17 62 2表12157346图202157346图1分析们可以选取某一个点k的条件只是它的父节点已经被选取或者它自己为根节点；而且我们不论如(何取k的子孙节点，都不会影响到它父节点的选取情况，这满足无后效性原则。于是我们猜测，是不是可以以节点为阶段，进行动态规划呢？我们用函数f(i,j)表示以第i个节点为父节点，取j个子节点的最佳代价，则：可是如此规划，其效率与搜索毫无差别，虽然我们可以再次用动态规划来使它的复杂度变为平方级，但显得过于麻烦。改造树转变为二叉树。如果两节点a,b同为兄弟，则将b设为a的右节点；如果节点b是节点a的儿子，则将节点b设为
8、节点a的左节点。树改造完成后如图3。我们用函数f(I,j)表示以第i个节点为父节点，取j个子节点的最佳代价，这和前一个函数表示的意义是一致的，但方程有了很大的改变：023014765图3转化为二叉树求解1=i=m,1=j=n,0=kj 这个方程的时间复杂度最大为n3，十分优秀了。在具体实现这道题时，我们可以自顶而下，用递归进行树的遍历求解 例三 河流(IOI2005) 一颗有N+1个结点的树，树中的每个结点可能会生产出一些产品。这些产品要么就地加工（要有加工厂才行），要么运送到它的父亲结点那儿去。现在在整棵树的根结点处已经有了一个产品加工厂，而且所有的产品最终必须在某个加工厂加工才行。由于运费
9、昂贵，不可能将所有的产品都运送到根节点处加工。现在决定在树中的某些结点新增总共K个加工厂，现在要你选择这K个加工厂的厂址。 假设结点i会生产出Wi吨产品，它的父结点是Pi。而它到它的父结点的路径的长度是Ui。运费的计算是每运送1顿的货物，每单位长度收取1的费用。根节点的编号为0。例三 河流(IOI2005)例如右图，0节点是根节点，如果要新增两个工厂，最佳方案是建在2、3两个节点上，这样总的费用为：1*1（1号）+1*3（4号）=4由于题目中给出的树是多叉树，不便于进行动态规划。我们先利用儿子兄弟表示法，将多叉树转化为二叉树。 进行了相关的转化之后，设f(i,j,k)表示在新树中，以i结点为根的子树中，分配k个加工厂。并且离i结点最近的加工厂在j结点的情况下。i结点及其子树内的所有产品，加工所需要的费用。转移方程很容易就可以写出来：总时间复杂度为O(N2K2)。例三 河流(IOI2005)
