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