第4章动态规划.ppt

《第4章动态规划.ppt》由会员分享，可在线阅读，更多相关《第4章动态规划.ppt（94页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第4章章 动态规划动态规划第四章 动态规划目录目录概述概述矩阵连乘问题矩阵连乘问题凸多边形最优三角剖分凸多边形最优三角剖分最长公共子序列问题最长公共子序列问题加工顺序问题加工顺序问题0-1背包问题背包问题最优二叉查找树最优二叉查找树教学目标理解动态规划的思想理解动态规划的思想掌握动态规划、分治法及贪心法的异同掌握动态规划、分治法及贪心法的异同掌握动态规划的基本要素掌握动态规划的基本要素掌握动态规划的设计步骤掌握动态规划的设计步骤通过实例学习，掌握动态规划设计的策略通过实例学习，掌握动态规划设计的策略学习动态规划的意义学习动态规划的意义动态规划问世以来，在经济管理、生产调度、工动态规划问世以来

2、，在经济管理、生产调度、工程技术和程技术和最优控制最优控制等方面得到了广泛的应用，例等方面得到了广泛的应用，例如最短路线、库存管理、资源分配、设备更新、如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方排序、装载等问题，用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解法求解更为方便。虽然动态规划主要用于求解以以时间划分阶段时间划分阶段的动态过程的优化问题，但是一些的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶划），只要人为地引进时间因素

3、，把它视为多阶段决策过程，也可以用动态规划方法方便地求解，段决策过程，也可以用动态规划方法方便地求解，因此研究该算法具有很强的实际意义。因此研究该算法具有很强的实际意义。动态规划算法通常用于求解具有动态规划算法通常用于求解具有某种最优性质的某种最优性质的问题，问题，动态规划的基本思想动态规划的基本思想基本思想基本思想 将待求解问题分解成若干个子问题，经将待求解问题分解成若干个子问题，经分解得到的子问题往往分解得到的子问题往往不是互相独立不是互相独立的。先的。先求解子问题，然后从这些子问题的解求解子问题，然后从这些子问题的解构造构造得得到原问题的解。到原问题的解。动态规划的解题步骤动态规划的解题

4、步骤（1）分析最优解的性质，刻画最优解的结构特）分析最优解的性质，刻画最优解的结构特征征考察是否适合采用动态规划法。考察是否适合采用动态规划法。（2）递归地定义最优值（即建立递归式或动态）递归地定义最优值（即建立递归式或动态规划方程）。规划方程）。（3）以自底向上的方式计算出最优值，并记录）以自底向上的方式计算出最优值，并记录相关信息。相关信息。（4）根据计算最优值时得到的信息，构造出最）根据计算最优值时得到的信息，构造出最优解。优解。动态规划的基本要素最优子结构性质最优子结构性质子问题重叠性质子问题重叠性质递归算法求解问题时，每次产生的子问题并不总是新问递归算法求解问题时，每次产生的子问题并

5、不总是新问题，有些子问题出现多次，这种性质称为子问题的重叠题，有些子问题出现多次，这种性质称为子问题的重叠性质。性质。在应用动态规划时，对于重复出现的子问题，只需在第在应用动态规划时，对于重复出现的子问题，只需在第一次遇到时就加以解决，并把已解决的各个子问题的解一次遇到时就加以解决，并把已解决的各个子问题的解储存在表中，便于以后遇到时直接引用，从而不必重新储存在表中，便于以后遇到时直接引用，从而不必重新求解，可大大提高解题的效率。求解，可大大提高解题的效率。自底向上的求解方式自底向上的求解方式矩阵连乘矩阵连乘问题描述问题描述给定给定n个矩阵个矩阵A1,A2,A3,An，其中，其中Ai与与Ai+

6、1(i=1,2,3,n-1)是可乘的。是可乘的。用加括号的方法表示矩阵连乘的次序，不同加括用加括号的方法表示矩阵连乘的次序，不同加括号的方法所对应的计算次序是不同的。号的方法所对应的计算次序是不同的。完全加括号的矩阵连乘积（1）单个矩阵是完全加括号的；（2）矩阵连乘积 是完全加括号的，则 可 表示为2个完全加括号的矩阵连乘积 和 的乘积并加括号，即 16000,10500,36000,87500,34500u完全加括号的矩阵连乘积可递归地定义为：完全加括号的矩阵连乘积可递归地定义为：u设有四个矩阵设有四个矩阵 ，它们的维数分别是：，它们的维数分别是：u总共有五中完全加括号的方式总共有五中完全加

7、括号的方式矩阵连乘问题n给定给定n n个矩阵个矩阵 ，其中其中 与与 是可乘是可乘的，的，。考察这。考察这n n个矩阵的连乘积个矩阵的连乘积 n由于矩阵乘法满足结合律，所以计算矩阵的连乘可以由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。的方式来确定。n若一个矩阵连乘积的计算次序完全确定，也就是说该若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用连乘积已完全加括号，则可以依此次序反复调用2 2个矩个矩阵相乘的标准算法计算出矩阵连乘积阵相乘的标准算法计算

8、出矩阵连乘积矩阵连乘问题 给定给定n个矩阵个矩阵A1,A2,An，其中，其中Ai与与Ai+1是可乘的，是可乘的，i=1,2,n-1。如何确定计算矩阵连乘积的计算次序，使。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。得依此次序计算矩阵连乘积需要的数乘次数最少。u穷举法穷举法：列举出所有可能的计算次序，并计算出每一种计列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。计算次序。算法复杂度分析：算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序为P(n)

9、。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1An)可以得到关于P(n)的递推式如下：矩阵连乘问题u穷举法穷举法u动态规划动态规划将矩阵连乘积将矩阵连乘积 简记为简记为Ai:j，这里，这里ij 考察计算考察计算Ai:j的最优计算次序。设这个计算次序在矩阵的最优计算次序。设这个计算次序在矩阵Ak和和Ak+1之间将矩阵链断开，之间将矩阵链断开，ikj，则其相应完全，则其相应完全加括号方式为加括号方式为计算量：计算量：Ai:k的计算量加上的计算量加上Ak+1:j的计算量，再加上的计算量，再加上Ai:k和和Ak+1:j相乘的计算量相乘的计算量分析最优解的结构特征：计算

10、特征：计算Ai:j的最优次序所包含的计算矩的最优次序所包含的计算矩阵子链阵子链 Ai:k和和Ak+1:j的次序也是最优的次序也是最优的。的。矩阵连乘计算次序问题的最优解包含着其子问矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为题的最优解。这种性质称为最优子结构性质最优子结构性质。问题的最优子结构性质是该问题可用动态规划问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。算法求解的显著特征。建立递归关系n设计算设计算Ai:j，1ijn，所需要的最少数乘次数，所需要的最少数乘次数mi,j，则原问题的最优值为，则原问题的最优值为m1,n n当当i=j时，时，Ai:j=Ai:

11、i，因此，因此，mi,i=0，i=1,2,nn当当ij时，时，可以递归地定义可以递归地定义mi,j为：为：这里 的维数为 的位置只有的位置只有 种种可能可能计算最优值n对于对于1ijn不同的有序对不同的有序对(i,j)对应于不同的子问对应于不同的子问题。因此，不同子问题的个数最多只有题。因此，不同子问题的个数最多只有n由此可见，在递归计算时，由此可见，在递归计算时，许多子问题被重复计算多许多子问题被重复计算多次次。这也是该问题可用动态规划算法求解的又一显著。这也是该问题可用动态规划算法求解的又一显著特征。特征。n用动态规划算法解此问题，可依据其递归式以自底向用动态规划算法解此问题，可依据其递归

12、式以自底向上的方式进行计算。在计算过程中，保存已解决的子上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法到多项式时间的算法例:要计算矩阵连乘积A1A2A3A4A5A6，其中各矩阵的维数分别为：A1A2A3A4A5A630*3535*1515*55*1010*2020*25计算最优值计算最优值:设计算设计算Ai:j，1ijn，所需要的最少数乘次，所需要的最少数乘次数数mi,j，则原问题的最优值为，则

13、原问题的最优值为m1,n。那么，得到最优值的过程如下：那么，得到最优值的过程如下：(1)m11=0,m22=0,m33=0,m44=0,m55=0,m66=0(2)m12=30*35*15=15750(3)m13有如下两种情况：有如下两种情况：m12+m33+p0p2p3=15750+0+30*15*5=18000 m11+m23+p0p1p3=0+m23+30*35*5=7875(4)m23=35*15*5=2625 m13的值取以上的值取以上2个的最小值。个的最小值。(5)m14有如下有如下3种情况：种情况：m11+m24+p0p1p4 m12+m34+p0p2p4 m13+m44+p0p

14、3p4=7875+0+30*5*10=9375在此，需计算在此，需计算m24和和m34，取以上，取以上3个的最小值。个的最小值。(6)m15有如下有如下4种情况：种情况：m11+m25+p0p1p5 m12+m35+p0p2p4 m13+m45+p0p3p4=7875+1000+30*5*20=11875 m14+m55+p0p4p5在此，需计算在此，需计算m25、m35和和m45，取以上，取以上4个的最小个的最小值。值。(7)m16有如下有如下5种情况：种情况：m11+m26+p0p1p6 m12+m36+p0p2p6 m13+m46+p0p3p6=7875+m46+30*5*25=1512

15、5 m14+m56+p0p4p6 m15+m66+p0p5p6在此，需计算在此，需计算m26、m36、m46和和m56，取以，取以上上5个的最小值。个的最小值。m46=m44+m56+5*10*25=6250 m46=m45+m66+5*20*25=3500例如例如:求求m26有有4中情况，如下：中情况，如下：m22+m36+p1p2p6 m23+m46+p1p3p6 m24+m56+p1p4p6 m25+m66+p1p5p6 M26的值是这的值是这4个值中的最小值。个值中的最小值。矩阵连乘问题的最优值public static void matrixChain(int p,int m,int

16、 s)int n=p.length-1;for(int i=1;i=n;i+)mii=0;for(int r=2;r=n;r+)for(int i=1;i=n-r+1;i+)int j=i+r-1;mij=mi+1j+pi-1*pi*pj;sij=i;for(int k=i+1;k j;k+)int t=mik+mk+1j+pi-1*pk*pj;if(t mij)mij=t;sij=k;A1A2A3A4A5A63035351515551010202025算法复杂度分析：算法复杂度分析：算法matrixChain的主要计算量取决于算法中对r，i和k的3重循环。循环体内的计算量为O(1)，而3重循

17、环的总次数为O(n3)。因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。矩阵连乘问题的最优解构造最优解构造最优解 Sij中的数据中的数据k告诉我们计算矩阵告诉我们计算矩阵Ai:j的最佳方式应在矩阵的最佳方式应在矩阵Ak和和Ak+1之间之间断开断开,即最优的加括号方式为即最优的加括号方式为(Ai:k)(Ak+1:j)，由于，由于sij=k，用，用sij替换替换k.。从。从s1n记录的信息可知计记录的信息可知计算算A1:n的最优加括号方式为：的最优加括号方式为：(A 1:s1n)(A s1n+1:n)矩阵连乘问题的最优解构造最优解算法描述构造最优解算法描述:Void Trac

18、eback(int i,int j,int*a)if(i=j)return;Traceback(i,sij,s);Traceback(sij+1,j,s);Cout”Multiply A”i”,”sij;Cout”and A”(sij+1)”,”jendl;要输出要输出A1:n的最优计算次序只要调用的最优计算次序只要调用Traceback(1,n,s)即可。上面例子的最优计即可。上面例子的最优计算次序为：算次序为：(A1(A2A3)(A4A5)A6)算法设计算法设计步骤步骤1：确定合适的数据结构。采用数组：确定合适的数据结构。采用数组m来存放各个子问题的最优值，数组来存放各个子问题的最优值，数

19、组s来存放各个子问题的最优决策来存放各个子问题的最优决策;步骤步骤2：初始化。令：初始化。令mii=0，sii0，其中，其中i=1,2,n；步骤步骤3：循环阶段。：循环阶段。步骤步骤3-1：按照递归关系式计算：按照递归关系式计算2个矩阵个矩阵AiAi+1相乘时的最优值并将其存入相乘时的最优值并将其存入mii+1，同时将最优决策记入，同时将最优决策记入sii+1，i=1,2,n-1；步骤步骤3-2：按照递归关系式计算：按照递归关系式计算3个矩阵个矩阵AiAi+1Ai+2相乘时的最优值并将其存入相乘时的最优值并将其存入mii+2，同时将最优决策记入，同时将最优决策记入sii+2，i=1,2,n-2

20、；依此类推，直到依此类推，直到 步骤步骤3-(n-1)：按照递归关系式计算：按照递归关系式计算n个矩阵个矩阵A1A2An相乘时的最优值并将其相乘时的最优值并将其存入存入m1n，同时将最优决策记入，同时将最优决策记入s1n。至此，至此，m1n即为原问题的最优值。即为原问题的最优值。步骤步骤4：根据数组：根据数组s记录的最优决策信息来构造最优解。记录的最优决策信息来构造最优解。步骤步骤4-1：递归构造：递归构造A1As1n的最优解，直到包含一个矩阵结束；的最优解，直到包含一个矩阵结束；步骤步骤4-2：递归构造：递归构造As1n+1An的最优解，直到包含一个矩阵结束；的最优解，直到包含一个矩阵结束；

21、步骤步骤4-3：将步骤：将步骤4-1和步骤和步骤4-2递归的结果加括号。递归的结果加括号。构造实例求矩阵求矩阵A1（32）、）、A2（25）、）、A3（510）、）、A4（102）和）和A5（23）连乘的最佳计算次序。）连乘的最佳计算次序。表4-6 实例最优值mij 表4-7 实例最优决策sijmijA1A2A3A4A5sijA1A2A3A4A5A1030160132150A101111A20100120132A20224A30100130A3034A4060A404A50A50递归构造最优解算法分析语句语句int t=mik+mk+1j+pi-1*pk*pj;为算法为算法MatrixChai

22、n的基本语句，最坏情况下该语句的执行次数为的基本语句，最坏情况下该语句的执行次数为O(n3)，故该算法的最坏时间复杂性为，故该算法的最坏时间复杂性为O(n3)。构造最优解的构造最优解的Traceback算法的时间主要取决于递归。最坏算法的时间主要取决于递归。最坏情况下时间复杂性的递归式为：情况下时间复杂性的递归式为：解此递归式得解此递归式得T(n)=O(n)。凸多边形最优三角剖分凸多边形最优三角剖分 基本概念基本概念一个简单多边形及其内部构成一个闭凸集时，称该简单一个简单多边形及其内部构成一个闭凸集时，称该简单多边形为凸多边形多边形为凸多边形。凸多边形的不相邻的两个顶点连接的直线段称为凸多边凸

23、多边形的不相邻的两个顶点连接的直线段称为凸多边形的弦形的弦。凸多边形的三角剖分指将一个凸多边形分割成互不相交凸多边形的三角剖分指将一个凸多边形分割成互不相交的三角形的弦的集合的三角形的弦的集合。给定凸多边形及定义在边、弦构成的三角形的权函数，给定凸多边形及定义在边、弦构成的三角形的权函数，最优三角剖分即不同剖分方法所划分的各三角形上权函最优三角剖分即不同剖分方法所划分的各三角形上权函数之和最小的三角剖分。数之和最小的三角剖分。三角剖分的结构将图将图4-6中的叶子结点中的叶子结点vivi+1与矩阵与矩阵Ai+1(i=0,1,2,3,4)对应，则图对应，则图4-6和图和图4-4所示的二叉树是一样的

24、。因此，所示的二叉树是一样的。因此，n+1边形的三角剖分边形的三角剖分与与n个矩阵连乘的计算次序是一一对应的。可见，个矩阵连乘的计算次序是一一对应的。可见，凸多边形最优剖凸多边形最优剖分问题的解决方法和矩阵连乘问题相似。分问题的解决方法和矩阵连乘问题相似。三角剖分和矩阵连乘的对应设有四个矩阵A1A2A3A4连乘的情况有：A1(A2(A3A4)(A1(A2A3)A4(A1A2)(A3A4)A1(A2A3)A4)(A1A2)A3)A4凸多边形三角剖分：三角剖分和矩阵连乘的对应A1(A2(A3A4)(A1(A2A3)A4(A1A2)(A3A4)A1(A2A3)A4)(A1A2)A3)A4三角剖分和矩

25、阵连乘的对应结论：凸多边形的最优三角剖分等价于矩阵连乘积问题。最优子结构性质分析将v0v6的凸多边形分为三部分：(v0v1v2v3):源凸多边形的一个子凸多边形(v0v3v6)：三角形(v3v4v5v6)：源凸多边形的一个子凸多边形三角形(v0v3v6)的两条边(v0v3)和(v3v6)是源凸多边形三角剖分的两条玄。那么，如果(v0v3)和(v3v6)的和最小，有v0v3一定是子凸多边形(v0v1v2v3)的最小三角剖分玄，v3v6一定是凸多边形(v3v4v5v6)的最小三角剖分玄最优子结构性质分析设设v0vkvn是将是将n+1边形边形P=v0,v1,vn分成三部分分成三部分v0,v1,vk、

26、vk,vk+1,vn和和v0,vk,vn的最佳剖分方的最佳剖分方法，那么凸多边形法，那么凸多边形v0,v1,vk的剖分一定是最优的，的剖分一定是最优的，vk,vk+1,vn的剖分也一定是最优的。的剖分也一定是最优的。设设v0,v1,vn三角剖分的权函数之和为三角剖分的权函数之和为c，v0,v1,vk三角剖分的权函数之和为三角剖分的权函数之和为a，vk,vk+1,vn三角剖分的权三角剖分的权函数之和为函数之和为b，三角形，三角形v0vkvn的权函数为的权函数为w(v0vkvn)，则，则c=a+b+w(v0vkvn)。如果如果c是最小的，则一定包含是最小的，则一定包含a和和b都是最小的。如果都是最

27、小的。如果a不是最不是最小的，则它所对应的小的，则它所对应的v0,v1,vk的三角剖分就不是最优的。的三角剖分就不是最优的。那么，对于凸多边形那么，对于凸多边形v0,v1,vk来说，肯定存在最优的三来说，肯定存在最优的三角剖分，设角剖分，设v0,v1,vk的最优三角剖分对应的权函数之和的最优三角剖分对应的权函数之和为为a(aa)，用，用a代替代替a得到得到c=a+b+w(v0vkvn)，则，则cc，这，这说明说明c对应的对应的v0,v1,vn的三角剖分不的三角剖分不是是最优的，产生矛最优的，产生矛盾。故盾。故a一定是最小的。同理，一定是最小的。同理，b也是最小的。最优子结构性也是最小的。最优子

28、结构性质得证。质得证。建立最优值的递归关系式设设mij表示表示vi-1vivj最优三角剖分权函数最优三角剖分权函数之和，之和，i=j时表示一条直线段，将其看作退时表示一条直线段，将其看作退化多边形，其权函数为化多边形，其权函数为0。则。则最长公共子序列 一个给定序列的子序列是：一个给定序列的子序列是：在该序列中在该序列中删去若干元素后得到的序列。删去若干元素后得到的序列。公共子序列：公共子序列：给定两个序列给定两个序列X和和Y，当另，当另一个序列一个序列Z既是既是X的子序列又是的子序列又是Y的子序列时，的子序列时，称称Z是序列是序列X和和Y的公共子序列。的公共子序列。最长公共子序列问题：最长公

29、共子序列问题：给定两个序列给定两个序列X=X=和和Y=Y=，找出，找出X X和和Y Y的一个最长公共子序列。的一个最长公共子序列。例如：例如：X=A,B,C,B,D,A,B,Y=B,D,C,A,B,A 则序则序列列B,C,A是是X和和Y的一个公共子序列。但它不是的一个公共子序列。但它不是X和和Y的一个最长公共子序列。序列的一个最长公共子序列。序列B,C,B,A是是X和和Y的的一个公共子序列，它的长度是一个公共子序列，它的长度是4，而且它是，而且它是X和和Y的一的一个最长公共子序列。因为，个最长公共子序列。因为，X和和Y没有长度大于没有长度大于4的公的公共子序列。它的另一个解是共子序列。它的另一

30、个解是B,C,A,B。该问题的答。该问题的答案不唯一案不唯一.最长公共子序列的形式化描述基本概念基本概念（1）子序列）子序列给定序列给定序列 X=x1,x2,xn、Z=z1,z2,zk，若若Z是是X的子序列，当且仅当存在一个严格递增的的子序列，当且仅当存在一个严格递增的下标序列下标序列 i1,i2,ik，对，对j1,2,k有有zj=x。（2）公共子序列）公共子序列给定序列给定序列X和和Y，序列，序列Z是是X的子序列，也是的子序列，也是Y的子序的子序列，则称列，则称Z是是X和和Y的公共子序列。的公共子序列。（3）最长公共子序列）最长公共子序列包含元素最多的公共子序列即为最长公共子序列。包含元素最

31、多的公共子序列即为最长公共子序列。最长公共子序列若给定序列若给定序列X=x1,x2,xm，则另一序列，则另一序列Z=z1,z2,zk，是，是X的子序列是指的子序列是指存在一个严格递存在一个严格递增下标序列增下标序列i1,i2,ik使得对于所有使得对于所有j=1,2,k有：有：zj=xij。例如，序列。例如，序列Z=B，C，D，B是序列是序列X=A，B，C，B，D，A，B的子序列，相应的递增下标序的子序列，相应的递增下标序列为列为12，23，35，47。给定给定2个序列个序列X和和Y，当另一序列，当另一序列Z既是既是X的子序列又的子序列又是是Y的子序列时，的子序列时，称称Z是序列是序列X和和Y的

32、的公共子序列公共子序列。给定给定2 2个序列个序列X=xX=x1 1,x,x2 2,x xm m 和和Y=yY=y1 1,y,y2 2,y yn n，找，找出出X X和和Y Y的最长公共子序列。的最长公共子序列。最长公共子序列的结构用动态规划算法可有效地解此问题。用动态规划算法可有效地解此问题。解最长公共子序列问题最容易想到的算法是穷举搜索法。解最长公共子序列问题最容易想到的算法是穷举搜索法。分别找出分别找出X X和和Y Y的所有子序列，再搜索它们的最长公共子序列。的所有子序列，再搜索它们的最长公共子序列。穷举搜索法需要指数时间。穷举搜索法需要指数时间。1、最长公共子序列的结构（问题的最优子结

33、构性质）、最长公共子序列的结构（问题的最优子结构性质）设序列设序列X=x1,x2,xm和和Y=y1,y2,yn的最长公共子序列的最长公共子序列为为Z=z1,z2,zk，则，则(1)若若xm=yn，则，则zk=xm=yn，且，且zk-1是是xm-1和和yn-1的最长公共子序的最长公共子序列。列。(2)若若xmyn且且zkxm，则，则Z是是xm-1和和Y的最长公共子序列。的最长公共子序列。(3)若若xmyn且且zkyn，则，则Z是是X和和yn-1的最长公共子序列。的最长公共子序列。由此可见，由此可见，2个序列的最长公共子序列包含了这个序列的最长公共子序列包含了这2个序列的前缀个序列的前缀的最长公共

34、子序列。因此，最长公共子序列问题具有的最长公共子序列。因此，最长公共子序列问题具有最优子结最优子结构性质构性质。子问题的递归结构2、子问题的递归结构（建立递归关系）、子问题的递归结构（建立递归关系）由最优子结构性质可知，要找出由最优子结构性质可知，要找出X和和Y的最长公共子序列可按以下方式递归地进行：的最长公共子序列可按以下方式递归地进行：（1）当）当xm=yn时，找出时，找出Xm-1和和Yn-1的最长公共子序的最长公共子序列。列。（2）当）当xmyn时，必须解两个子问题，找出时，必须解两个子问题，找出Xm-1和和Y的一个最长公共子序列及的一个最长公共子序列及X和和Yn-1的一个最长公的一个最

35、长公共子序列。这两个公共子序列中共子序列。这两个公共子序列中较长者较长者即为即为X和和Y的一个最长公共子序列。的一个最长公共子序列。由此递归结构容易看到最长公共子序列问题具有子问题重叠由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。因为，在计算性质。因为，在计算X和和Y的最长公共子序列时，可能要计算的最长公共子序列时，可能要计算X和和Yn-1及及Xm-1和和Y的最长公共子序列，而这两个子问题都包的最长公共子序列，而这两个子问题都包含一个公共子问题，即计算含一个公共子问题，即计算Xm-1和和Yn-1的最长公共子序列。的最长公共子序列。子问题的递归结构由最长公共子序列问题的最优子结构性质

36、建立子问题最优值由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用的递归关系。用cij记录序列和的最长公共子序列的长度。记录序列和的最长公共子序列的长度。其中，其中，Xi=x1,x2,xi；Yj=y1,y2,yj。当。当i=0或或j=0时，时，空序列是空序列是Xi和和Yj的最长公共子序列。故此时的最长公共子序列。故此时Cij=0。其他情。其他情况下，由最优子结构性质可建立递归关系如下：况下，由最优子结构性质可建立递归关系如下：计算最优值3 3、计算最优值、计算最优值 直接利用递归式写出一个计算直接利用递归式写出一个计算cij的递归算法。的递归算法。例如：设所给的例如：设所给的2

37、个序列为个序列为X=A,B,C,B,D,A,B和和Y=B,D,C,A,B,A 由算法由算法LCSLength和和LCS计算出的计算出的结果如图结果如图3-3所示所示计算最优值LCS：另一个解另一个解B,C,A,B计算最优值由于在所考虑的子问题空间中，总共有由于在所考虑的子问题空间中，总共有(mn)个不同的子问题，个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。因此，用动态规划算法自底向上地计算最优值能提高算法的效率。Algorithm lcsLength(x,y,b)1:mx.length-1;2:ny.length-1;3:ci0=0;c0i=0;4:for(int

38、 i=1;i=m;i+)5:for(int j=1;j=cij-1)10:cij=ci-1j;11:bij=2;12:else 13:cij=cij-1;14:bij=3;构造最长公共子序列构造最长公共子序列Algorithm lcs(int i,int j,char x,int b)if(i=0|j=0)return;if(bij=1)lcs(i-1,j-1,x,b);System.out.print(xi);else if(bij=2)lcs(i-1,j,x,b);else lcs(i,j-1,x,b);算法的改进在算法在算法lcsLength和和lcs中，可进一步将数组中，可进一步将数组

39、b省去。省去。事实上，数组元素事实上，数组元素cij的值仅由的值仅由ci-1j-1，ci-1j和和cij-1这这3个数组元素的值所确定。对于给定的数个数组元素的值所确定。对于给定的数组元素组元素cij，可以不借助于数组，可以不借助于数组b而仅借助于而仅借助于c本身本身在时间内确定在时间内确定cij的值是由的值是由ci-1j-1，ci-1j和和cij-1中哪一个值所确定的。中哪一个值所确定的。如果只需要计算最长公共子序列的长度，则算法的空如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算间需求可大大减少。事实上，在计算cij时，只用时，只用到数组到数组c的第的第i行和

40、第行和第i-1行。因此，用行。因此，用2行的数组空间行的数组空间就可以计算出最长公共子序列的长度。进一步的分析就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至还可将空间需求减至O(min(m,n)。0-1背包问题问题描述问题描述0-1背包问题可描述为：背包问题可描述为：n个物品和个物品和1个背包。对物品个背包。对物品i，其价值为其价值为vi，重量为，重量为wi，背包的容量为，背包的容量为W。如何选取物品。如何选取物品装入背包，使背包中所装入的物品的总价值最大？装入背包，使背包中所装入的物品的总价值最大？约束条件：约束条件：（4-7）目标函数：目标函数：（4-8）于是，问题归结为

41、寻找一个满足约束条件（于是，问题归结为寻找一个满足约束条件（4-7），并使），并使目标函数（目标函数（4-8）达到最大的解向量）达到最大的解向量X=(x1,x2,xn)。最优子结构性质分析假设（假设（x1,x2,xn)是所给是所给0-1背包问题的背包问题的一个最优解，则（一个最优解，则（x2,xn）是下面相应）是下面相应子问题的一个最优解：子问题的一个最优解：约束条件：约束条件：目标函数：目标函数：运用反证法来证明运用反证法来证明建立最优值的递归关系式令令Cij=C0j=Ci0=0 （4-10)n（4-11)算法设计求装入背包的最大价值步骤步骤1：设计算法所需的数据结构。采用数组：设计算法所需

42、的数据结构。采用数组wn来存放来存放n个物品的重量；数组个物品的重量；数组vn来存放来存放n个物品的价值，背包个物品的价值，背包容量为容量为W，数组，数组Cn+1W+1来存放每一次迭代的执行结来存放每一次迭代的执行结果；数组果；数组xn用来存储所装入背包的物品状态；用来存储所装入背包的物品状态；步骤步骤2：初始化。按式：初始化。按式(4-10)初始化数组初始化数组C；步骤步骤3：循环阶段。按式（：循环阶段。按式（4-11）确定前）确定前i个物品能够装入个物品能够装入背包的情况下得到的最优值；背包的情况下得到的最优值；步骤步骤3-1：i=1时，求出时，求出C1j，1jW；步骤步骤3-2：i=2时

43、，求出时，求出C2j，1jW；依此类推，直到依此类推，直到步骤步骤3-n：i=n时，求出时，求出CnW。此时，。此时，CnW便是最便是最优值；优值；算法设计确定装入背包的具体物品从从CnW的值向前推，如果的值向前推，如果CnW Cn-1W，表明，表明第第n个物品被装入背包，则个物品被装入背包，则xn=1，前，前n-1个物品被装入容量个物品被装入容量为为W-wn的背包中；否则，第的背包中；否则，第n个物品没有被装入背包，则个物品没有被装入背包，则xn=0，前，前n-1个物品被装入容量为个物品被装入容量为W的背包中。依此类推，的背包中。依此类推，直到确定第直到确定第1个物品是否被装入背包中为止。由

44、此，得到个物品是否被装入背包中为止。由此，得到下面关系式：下面关系式：（4-12）按照式（按照式（4-12），从），从CnW的值向前倒推，即的值向前倒推，即j初始为初始为W，i初始为初始为n，即可确定装入背包的具体物品。，即可确定装入背包的具体物品。构造实例【例例4-8】有有5个个物物品品，其其重重量量分分别别为为2,2,6,5,4，价价值值分分别别为为6,3,5,4,6。背背包包容容量量为为10，物物品品不不可可分分割割，求求装装入入背背包的物品和获得的最大价值。包的物品和获得的最大价值。行行i表示物品，列表示物品，列j表示背包容量，表中数据表示表示背包容量，表中数据表示Cij 012345

45、678910000000000000100666666666200669999999300669999111114400669991011131450066991212151515确定装入背包的具体物品从从CnW的值根据式（的值根据式（4-12）向前推，最终可求出装入背包）向前推，最终可求出装入背包的具体物品，即问题的最优解。的具体物品，即问题的最优解。初始时，初始时，j=W，i=5。如果如果Cij=Ci-1j，说明第，说明第i个物品没有被装入背包，则个物品没有被装入背包，则xi=0；如果如果CijCi-1j，说明第，说明第i个物品被装入背包，则个物品被装入背包，则xi=1，j=j-wi。由于

46、由于CnW=C510=15C410=14，说明物品，说明物品5被装入被装入了背包，因此了背包，因此x5=1，且更新，且更新j=j-w5=10-4=6。由于。由于C4j=C46=9=C36，说明物品，说明物品4没有被装入背包，因没有被装入背包，因此此x4=0；由于；由于C3j=C36=9=C26=9，说明物品，说明物品3没有没有被装入背包，因此被装入背包，因此x3=0。由于。由于C2j=C26=9C16=6，说明物品，说明物品2被装入了背包，因此被装入了背包，因此x2=1，且更新，且更新j=j-w2=6-2=4。由于。由于C1j=C14=6C04=0，说明物品，说明物品1被装入被装入了背包，因此

47、了背包，因此x1=1，且更新，且更新j=j-w1=4-2=2。最终可求得装。最终可求得装入背包的物品的最优解入背包的物品的最优解X=(x1,x2,xn)=(1,1,0,0,1)。算法描述Int KnapSack(int n,int w,int v)int I,j,cnn,xn;for(i=0;i=n;i+)ci0=0;for(i=0;i=n;i+)c0i=0;for(i=1;i=n;i+)for(j=1;j=w;j+)if(j0;i-)if(cijci-1j)xi=1;j-=wi;else xi=0;return cnw;算法分析在算法在算法KnapSack中，第中，第3个循环是两层嵌套的个循

48、环是两层嵌套的for循环，循环，为此，可选定语句为此，可选定语句if(j2n时，算法需要时，算法需要O(n2n)的计的计算时间。因此，在这里设计了对算法算时间。因此，在这里设计了对算法KnapSack的改进方的改进方法，采用该方法可克服这两大缺点。法，采用该方法可克服这两大缺点。改进算法改进思路改进思路:由由Cij的递归式的递归式（4-11）容易证明：）容易证明：在一般情况下，对每在一般情况下，对每一个确定的一个确定的i(1in)，函数，函数Cij是关于是关于变量变量j的阶梯状单调不的阶梯状单调不减函数（事实上，计减函数（事实上，计算算Cij的递归式在的递归式在变量变量j是连续变量，即是连续变

49、量，即为实数时仍成立）。为实数时仍成立）。跳跃点是这一类函数跳跃点是这一类函数的描述特征。在一般的描述特征。在一般情况下，函数情况下，函数Cij由其全部跳跃点唯一由其全部跳跃点唯一确定。确定。利用c(I,j)函数有跳跃点唯一确定的性质，对0-1背包问题的算法进行改进：1、对每一个确定的i(1=i=n),用一个表pi存储cij的全部跳跃点。对每一个确定的实数j，可以通过查找pi来确定cij的值。Pi中的全部跳跃点(j,cij)按j升序排列。由于cij是关于j的阶梯状单调不减函数，故pi中的全部跳跃点的cij值页是递增排列的。2、pi可以通过计算pi-1得到。cij是计算maxci-1j,ci-1

50、j-wi+vi得到的，因此，cij的全部跳跃点集（即pi）包含ci-1j的跳跃点集与ci-1j-wi+vi的跳跃点集qi-1的并集。3、在跳跃点集pi-1并qi-1时，按j由小到大排序，如果出现j增加，cij反而下降的点时，该点应该被舍弃。该舍弃点为受控跳跃点。4、在递归地有pi-1计算pi时，可先由pi-1计算出qi-1，然后合并pi-1和qi-1，并清除其中的受控跳跃点得到pi5、构造最优解例：用跳跃点算法求解例4-8的问题。(p106)算法描述Type GKnapSack(int n,Type w,Type v,Type w,Type*p,int x)int*head=new intn+