动态规划的模型构建.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,动态规划的模型构建,长沙市雅礼中学 朱全民,NOIP,的动态规划试题,加分二叉树,(2003),树型动态规划,合唱队形,(2004),线型动态规划,青蛙过河,(2005),线型动态规划,能量项链,(2006),合并类型动态规划,金明的预算方案,(2006),资源类型动态规划,矩阵取数游戏,(2007),规则类型动态规划,传纸条,(2008),规则类型动态规划,星球贸易,(2009),线型动态规划,乌龟棋,(2010),线型动态规划,引例：数字三角形,如图所示的数字三角形中,从第一行的数字出发,每次向左下或右下走一格，直到最后一行,要求沿途数字之和最大,1,3 2,4 10 1,4 3 2 20,动态规划的基本概念,阶段：把问题分成几个相互联系的有顺序的几个环节，这些环节即称为阶段。,状态：某一阶段的出发位置称为状态。通常一个阶段包含若干状态。,决策：从某阶段的一个状态演变到下一个阶段某状态的选择。,策略：由开始到终点的全过程中，由每段决策组成的决策序列称为全过程策略，简称策略。,动态规划的基本概念,状态转移方程：前一阶段的终点就是后一阶段的起点，前一阶段的决策选择导出了后一阶段的状态，这种关系描述了由,k,阶段到,k+1,阶段状态的演变规律，称为状态转移方程。,目标函数与最优化概念：目标函数是衡量多阶段决策过程优劣的准则。最优化概念是在一定条件下找到一个途径，经过按题目具体性质所确定的运算以后，使全过程的总效益达到最优。,最优化原理,一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。,简而言之，一个最优化策略的子策略总是最优的。,最优化原理是动态规划的基础，任何问题，如果失去了最优化原理的支持，就不可能用动态规划方法计算。,无后效性,“,过去的步骤只能通过当前状态影响未来的发展，当前的状态是历史的总结”。这条特征说明动态规划只适用于解决当前决策与过去状态无关的问题。状态，出现在策略任何一个位置，它的地位相同，都可实施同样策略，这就是无后效性的内涵。,举例,最短路（不带负权边，带负权边）,动态规划的解题步骤,划分阶段：注意阶段一定要是有序的或者是可排序的，否则问题就无法求解。,选择状态：状态的选择要满足无后效性。,确定决策：决策决定着状态的转移，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。,写出状态转移方程（包括边界条件和取值范围）：根据问题的性质（求最大,/,最小），用数学方程描述状态转移的方法和过程,编程实现？,循环,For i,For j,(dummy),递归,Solve(i,j,),If solved,fij,return,fij,(dummy),数字三角形求解,状态：,f(i,j,),表示走到第,i,行,j,列获得的最大值,状态转移方程,:,f(i,j,)=maxf(i-1,j),f(i-1,j+1)+ai,j,初始：,f(0,0)=0,问题,1,：求最短距离（,1,）,某人要从,S,1,前往,S,N,，其中,S,i,至,S,i+1,有若干种行进方式（步行，自行车，公交车，越野车，,etc,），分别要花费一定的时间,问最快到达的时间是多少？,分析,划分阶段、选择状态：,到达各个不同的地点作为一个阶段,一个阶段里就一个状态,用,Fi,表示从,S1,到达,Si,所需最短的时间,写出规划方程（包括边界条件）：,F1=0,Fi,=Fi-1+S,i-1,到达,S,i,所需花费的最短时间,问题,1,：求最短距离（,2,）,某人要从,S,1,前往,S,N,，其中,S,i,至,S,i+1,有若干种行进方式（步行，自行车，公交车，越野车，,etc,），分别要花费一定的时间，并且如果在一个地点选择切换行进方式，需要额外消耗一定的时间。,问最快到达的时间是多少？,分析,划分阶段、选择状态：,使用与上面一样的方案发现不可行，无法解决判定是否需要切换行进方式,加一维状态进行表示,用,fij,表示要从,S,1,到达,S,i,，在,S,i,时使用的出行方式为,j,，所需最短的时间,写出规划方程（包括边界条件）,思考？,必须在每个地点切换行进方式？,“,S,i,至,S,i+1,有若干种行进方式”为“,S,i,至,S,j,(j,i),有若干种行进方式”？,若为任意两点,S,i,至,S,j,之间都有若干种行进方式？,若在切换时候需要行进方式时须增加时间？,中途经过的地点不能超过,X,个，该如何处理？,若费用为负怎么办？,分析,设,f(i,),表示前,i,个数的最长不上升序列的长度。,则,f(i,)=maxf(j)+1,其中,j=,ai,这里,0ji=n,。,显然时间复杂度为,O(n,2,),。,上述式子的含义：找到,i,之前的某,j,，这个数不比第,i,个数小,对于所有的,j,取,f(j,),的最大值。,问题,2:,求最长公共子序列,给定的字符序列,X=,“,x,0,，,x,1,，,，,x,m-1”,，,序列,Y=,“,y,0,，,y,1,，,，,y,k-1”,是X,的子序列，存在,X,的一个严格递增下标序列,，使得对所有的,j=0,，,1,，,，,k-1,，有,x,ij,=,y,j,。,例如，,X=,“,ABCBDAB,”，,Y=,“,BCDB,”是,X,的一个子序列。,给出两个字串,S1,和,S2,，长度不超过,5000.,求这两个串的最长公共子序列长度。,动态规划,设,f(i,j,),表示,S,的前,i,位与,T,的前,j,位的最长公共子串长度。则有，,时间复杂度,O(n,*m),思考？,给出两个串，求最长公共子串？,给定两个字符串，求最小编辑次数使得两个字符串相等，所谓编辑，即删除、插入或修改某个字符。,给出一个串，求最小编辑次数，使得某个串变成回文串？,问题,3,：,01,背包问题,有,N,件物品,;,第,i,件物品,Wi,公斤,;,第,i,件物品价值,Ci,元,;,现有一辆载重,M,公斤的卡车,;,问选取装载哪些物品，使得卡车运送的总价值最大？,动态规划,可以按每个物品进行规划，同样每种物品有选和不选两种选择,设,F(i,j,),表示前,i,件物品载重为,j,的最大效益，则有,1=i=N,0=j=N,初值：,F(0,j)=0,F(N,M),即答案,显然时间复杂度为,O(NM),思考？,完全背包问题：即每个物品可取无限次。,多重背包问题：第,i,种物品可取,ni,次。,带条件背包问题：取某种物品，必须取另外一种物品的限制。,二维背包问题：物品分为两类，每类分别放到一个背包中。,每个物品有个编号，价值最大的前提下，所取物品组成的排列字典序最小。,问题,4,：石子合并,在一园形操场四周摆放,N,堆石子,(N100),现要将石子有次序地合并成一堆,.,规定每次只能选相临的两堆合并成一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序,由文件读入堆数,N,及每堆石子数,(20),(1),选择一种合并石子的方案,使得做,N-1,次合并,得分的总和最少,(2),选择一种合并石子的方案,使得做,N-1,次合并,得分的总和最大,输入数据,:,第一行为石子堆数,N;,第二行为每堆石子数,每两个数之间用一空格分隔,.,输出数据,:,从第,1,至第,N,行为得分最小的合并方案,.,第,N+1,行为空行,.,从,N+2,到,2N+1,行是得分最大的合并方案,.,示例,N=5,石子数分别为,3 4 6 5 4 2,。,用贪心法的合并过程如下：,第一次,3 4 6 5 4 2,得分,5,第二次,5 4 6 5 4,得分,9,第三次,9 6 5 4,得分,9,第四次,9 6 9,得分,15,第五次,15 9,得分,24,第六次,24,总分：,62,然而仔细琢磨后，发现更好的方案：,第一次,3 4 6 5 4 2,得分,7,第二次,7 6 5 4 2,得分,13,第三次,13 5 4 2,得分,6,第四次,13 5 6,得分,11,第五次,13 11,得分,24,第六次,24,总分：,61,显然，贪心法是错误的。,动态规划,用,datai,j,表示将从第,i,颗石子开始的接下来,j,颗石子合并所得的分值，,maxi,j,表示将从第,i,颗石子开始的接下来,j,颗石子合并可能的最大值，那么：,maxi,j,=,max(maxi,k+,maxi,+k,j,k+,datai,k,+,datai+k,j,k)(2=k=j),maxi,i,=0,同样的，我们用,mini,j,表示将第从第,i,颗石子开始的接下来,j,颗石子合并所得的最小值，可以得到类似的方程：,mini,j,=,min(mini,k+,mini,+k,j,k+,datai,k,+,datai+k,j,k)(0=k=j),mini,i,=0,这样，我们完美地解决了这道题。时间复杂度也是,O(n,3,),。,思考题：多边形,多角形是一个单人玩的游戏，开始时有一个,N,个顶点的多边形。如图，这里,N=4,。每个顶点有一个整数标记，每条边上有一个,“,+,”,号或,“,*,”,号。边从,1,编号到,N,。,第一步，一条边被拿走；随后各步包括如下：,选择一条边,E,和连接着,E,的两个顶点,V1,和,V2,；,得到一个新的顶点，标记为,V1,与,V2,通过边,E,上的运算符运算的结果。,最后，游戏中没有边，游戏的得分为仅剩余的一个顶点的值。,样例,写一个程序，对于给定一个多边形，计算出可能的最高得分，并且列出得到这个分数的过程。,问题,5,：,Robots,在一个,n*m,的棋盘内，一些格子里有垃圾要拾捡。现在有一个能捡垃圾的机器人从左上格子里出发，每次只能向右或者向下走。每次他到达一个点，就会自动把这个点内的垃圾拾掉。,问：最多能拾多少垃圾。在最多的情况下，有多少种方案？请举出一种方案来。,数据范围,:n=100,m=100,举例,最多能拾,5,块。有,4,种方法。,分析：,因为只能向右或者向下走。也就是说不能走回头路。于是考虑动态规划。,设,Fi,j,表示从,(1,1),点开始走到,(,i,j,),的时候，最多捡了多少垃圾。,Gi,j,表示在,fi,j,最大的时候，有多少种方案。,Ci,j,=1,表示,(,i,j,),点有垃圾。,Ci,j,=0,表示没有。,状态转移方程,根据,(,i,j,),只能从,(i-1,j),或者,(i,j-1),走过来。,于是,fi,j,=Maxfi-1,j,fi,j-1+ci,j.,怎么求,g(i,j,),？,可变成有向无环图来解决。,思考？,两个机器人同时捡垃圾，如何处理？,三个机器人呢？,若某些垃圾之间有联系，必须同时拾捡？,免费馅饼,SERKOI,最新推出了一种叫做,“,免费馅饼,”,的游戏。,游戏在一个舞台上进行。舞台的宽度为,W,格，天幕的高度为,H,格，游戏者占一格。开始时，游戏者站在舞台的正中央，手里拿着一个托盘。,游戏开始后，从舞台天幕顶端的格子中不断出现馅饼并垂直下落。游戏者左右移动去接馅饼。游戏者每秒可以向左或右移动一格或两格，也可以站在愿地不动。,馅饼有很多种，游戏者事先根据自己的口味，对各种馅饼依次打了分。同时在,8-308,电脑的遥控下，各种馅饼下落的速度也是不一样的，下落速度以格,/,秒为单位。当馅饼在某一秒末恰好到达游戏者所在的格子中，游戏者就收集到了这块馅饼。,写一个程序，帮助我们的游戏者收集馅饼，使得收集的馅饼的分数之和最大。,输入数据：,第一行,:,宽度,W,（,199,奇数）和高度,H,（,1 100,整数）,接下来给出了一块馅饼信息。由,4,个正整数组成，分别表示了馅饼的,初始下落时刻、水平位置、下落速度、分值。,游戏开始时刻为,0,。从,1,开始自左向右依次对水平方向的每格编号。,输出数据：,收集到的馅饼最大分数之和。,由上图可知，尽管下落了,4,个馅饼，但只能接到,3,个：,第,1,时刻可以接到分值为,5,的馅饼,第,2,时刻可以接到分值为,3,的馅饼,第,3,时刻可以接到分值为,4,的馅饼,因此馅饼的总分值为,5+3+4=12,问题,6,：加分二叉树,给定一个中序遍历为,1,2,3,n,的二叉树,每个结点有一个权值,定义二叉树的加分规则为：,左子树的加分,右子树的加分根的分数,若某个树缺少左子树或右子树，规定缺少的子树加分为,1,。,构造符合条件的二叉树,该树加分最大,输出其前序遍历序列,样例,中序遍历为,1,2,3,4,5,的二叉树有很多，下图是其中的三棵，其中第三棵加分最大，为,145.,分析,性质：中序遍历是按“左,-,根,-,右”方式进行遍历二叉树，因此二叉树左孩子遍历序列一定在根结点的左边，右孩子遍历序列一定在根结点的右边！,因此，假设二叉树的根结点为,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,)=,di,答案为,f(1,n),1=i=k=j=n,时间复杂度,O(n,3,),要构造这个树，只需记录每次的决策值，令,b(i,j,)=k,，表示中序遍历为,i,i+1,j,的二叉树的取最优决策时的根结点为,k,最后前序遍历这个树即可。,思考题：选课,大学里实行学分。每门课程都有一定的学分，学生只要选修了这门课并考核通过就能获得相应的学分。学生最后的学分是他选修的各门课的学分的总和。,每个学生都要选择规定数量的课程。其中有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。例如，,数据结构,必须在选修了,高级语言程序设计,之后才能选修。我们称,高级语言程序设计,是,数据结构,的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。为便于表述每门课都有一个课号，课号依次为,1,，,2,，,3,，,。,每个学生可选课程的总数是给定的。现在请你找出一种选课方案，使得你能得到学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。,输入,输入文件的第一行包括两个正整数,M,、,N,（中间用一个空格隔开）其中,M,表示待选课程总数（,1M1000),，,N,表示学生可以选的课程总数（,1NM),。,以下,M,行每行代表一门课，课号依次为,1,，,2,M,。每行有两个数（用一个空格隔开），第一个数为这门课的先修课的课号（若不存在先修课则该项为,0,），第二个数为这门课的学分。学分是不超过,10,的正整数。,输出,输出文件第一行只有一个数，即实际所选课程的学分总数。以下,N,行每行有一个数，表示学生所选课程的课号。,问题,7,：聚会的快乐,你要组织一个由你公司的人参加的聚会。你希望聚会非常愉快，尽可能多地找些有趣的热闹。但是劝你不要同时邀请某个人和他的上司，因为这可能带来争吵。给定,N,个人,(,姓名，他幽默的系数，以及他上司的名字,),，编程找到能使幽默系数和最大的若干个人。,【,输入,】,第一行一个整数,N(N100),。接下来有,N,行，每一行描述一个人的信息，信息之间用空格隔开。姓名是长度不超过,20,的字符串，幽默系数是在,0,到,100,之间的整数。,【,输出,】,所邀请的人最大的幽默系数和。,样例,【,样例,】,party.in,party.out,58,BART 1 HOMER,HOMER 2 MONTGOMERY,MONTGOMERY 1 NOBODY,LISA 3 HOMER,SMITHERS 4 MONTGOMERY,分析,首先，很显然公司的人员关系构成了一棵树。设,fa,为,a,参加会议的情况下，以他为根的子树取得的最大幽默值；,ga,为,a,不参加会议的情况下，以他为根的子树取得的最大幽默值。那么，状态转移方程就是：,fa,=gb,1,+gb,2,+gb,k,+1,ga,=max(fb,1,gb,1,)+max(fb,2,gb,2,)+,max(fb,k,gb,k,),其中,b,1,b,2,b,k,为,a,的子结点。,最后的答案就是,max(froot,groot,),，,root,是树,思考题：警卫安排,一个有,N,个区域的树结构上需要安排若干个警卫；,每个区域安排警卫所需要的费用是不同的；,每个区域的警卫都可以望见其相邻的区域，只要一个区域被一个警卫望见或者是安排有警卫，这个区域就是安全的；,任务：在确保所有区域都是安全的情况下，找到安排警卫的最小费用；,0n=720,；,联系方式,zhuquanmin,长沙市雅礼中学 朱全民,410007,