第3章动态规划1

1、12 学习要点学习要点: :理解动态规划算法的概念掌握动态规划算法的基本要素（1）最优子结构性质（2）重叠子问题性质掌握设计动态规划算法的步骤(1)找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值(3)以自底向上的方式计算出最优值(4)根据计算最优值时得到的信息，构造最优解。3p动态规划动态规划(dynamic programming)是运筹学的一个是运筹学的一个分支，是求解分支，是求解决策过程决策过程(decision process)最优化的数最优化的数学方法。学方法。p 20世纪世纪50年代初年代初美国数学家美国数学家R.E.Bellman等人在研等人在研究究多阶段决策过程多阶

2、段决策过程(multistep decision process)的优化的优化问题时，提出了著名的问题时，提出了著名的最优化原理最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方，逐个求解，创立了解决这类过程优化问题的新方法法动态规划。动态规划。p1957年出版了他的名著年出版了他的名著Dynamic Programming，这是该领域的第一本著作，标志着运筹学的一个新，这是该领域的第一本著作，标志着运筹学的一个新分支的创立。分支的创立。4生活中的实例n( 1) 汽车加

3、油问题: 设有路程长度为L 公里的公路上，分布着m 个加油站，它们的位置分别为p( i = 1，2，m) ，而汽车油箱加满油后( 油箱最多可以加油k 升) ，可以行驶n 公里。设计一个方案，使汽车经过此公路的加油次数尽量少( 汽车出发时是加满油的) 。5n( 2) 田忌与齐王赛马各有n 匹马参赛( n100) ，每场比赛赌注为1 两黄金，现已知齐王与田忌的每匹马的速度，并且齐王肯定是按马的速度从快到慢出场，现要你写一个程序帮助田忌计算他最好的结果是赢多少两黄金( 输用负数表示) 。6n( 3)有一个游戏室里有多个游戏室，并且这每个游戏室里还有多个游戏室，每个游戏室里面还有游戏室，依此类推。进入

4、每个游戏室都可得到一定的快乐，每个游戏室的门票价格都大于0，都有一个快乐值，并且只有进入了一个游戏室，才可以进入它内部的游戏室，小明现在有n 元钱，问最大能得到多少的快乐。7通过应用范例学习动态规划算法设计策略（1）矩阵连乘问题；（2）最长公共子序列；（3）最大子段和（4）凸多边形最优三角剖分；（5）多边形游戏； （6）图像压缩；（7）电路布线；（8）流水作业调度；（9）背包问题；（10）最优二叉搜索树。8n动态规划算法与分治法类似动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=9n但是,分解得到的子问题往往子问

5、题往往不是互相独立的不是互相独立的。不同子问题的数目常常只有多项式量级。n在用分治法求解时，有些子问题被重复计算了许多次。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)10n如果能够保存已解决的子问题的答案保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/

6、4)T(n/4)T(n/4)T(n/4) T(n/4)T(n)11n时间复杂度是O(p(n)的算法称为多项式时间算法，p(n)是关于n的多项式。不能够这样限制时间复杂度的算法被称为指数时间算法。n例如：时间复杂度为O(nlog(n)、O(n3)的算法都是多项式时间算法，时间复杂度为O(nlog(n)、O(n!)、O(2n)的算法是指数时间算法。12n找出最优解的性质，并刻画其结构特征。n递归地定义最优值。n以自底向上的方式计算最优值。n根据计算最优值时得到的信息，构造最优解。n13基本步骤。p动态规划算法常用于求解具有某种最优性质的问题.p可能有许多可行解, 希望找到具有最优值的那个解.13n

7、给定n个矩阵 ， 其中 与 是可乘的， 。考察这n个矩阵的连乘积 n由于矩阵乘法满足结合律矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。n若一个矩阵连乘积的计算次序完全确定，即连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算矩阵连乘积.,.,21nAAAiA1iA1,.,2 , 1ninAAA.2114（1）单个矩阵是完全加括号的；（2）矩阵连乘积A是完全加括号的，则A可 表示为2个完全加括号的矩阵连乘积B 和C 的乘积并加括号，即A=(BC) DCBA , , ,1050A4010B3040C530D)(DBCA)(

8、DCAB)(DBCA)(CDBA)(CDAB数乘次数:16000, 10500, 36000, 87500, 3450015n给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1，2，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。u穷举法穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。 算法复杂度分析算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1An),可以得到关于P(n)的递推

9、式如下：)/4()(11)()(1)(2/311nnPnnknPkPnPnnk16u穷举法穷举法u动态规划动态规划将矩阵连乘积 简记为Ai:j ，这里ij jiiAAA.1考察计算Ai:j的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，ikj，则其相应完全加括号方式为).)(.(211jkkkiiAAAAAA计算量：Ai:k的计算量加上Ak+1:j的计算量，再加上Ai:k和Ak+1:j相乘的计算量.动态规划法解矩阵连乘积最优计算次序问题的步骤如下:17n动态规划算法的第一步:刻画问题的最优解结刻画问题的最优解结构特征构特征.n特征：计算Ai:j的最优次序所包含的计算矩阵子链

10、 Ai:k和Ak+1:j的次序也是最优的。n矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质最优子结构性质。n问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。18n设计算Ai:j所需要的最少数乘次数为mi,j， 1ijn，则原问题的最优值为m1,n n当i=j时，Ai:j=Ai，因此，mi,i=0，i=1,2,nn当ij时，n可以递归地定义mi,j为：jkipppjkmkimjim1, 1,这里 的维数为 iAiipp1jipppjkmkimjijimjki, 1,min0,1jki 的位置只有 种可能kij 注意注意:(1) mi,j给出了最优值给出

11、了最优值,同时确定了最优次序中的断开位置同时确定了最优次序中的断开位置k: mi,j=mi,k+mk+1,j+pi-1pkpj(2) 若将对应于若将对应于mi,j的断开位置的断开位置k记为记为si,j, 在计算最优值在计算最优值mi,j后后, 可由可由si,j构造出相应的最优解构造出相应的最优解.19n对于1ijn不同的有序对有序对(i,j), 对应于不同的子问题。因此，不同子问题的个数最多只有n由此可见，在递归计算时，许多子问题被重复计算多许多子问题被重复计算多次次。这也是该问题可用动态规划算法求解的又一显著特征。n用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。n保存已解决

12、子问题答案,每个子问题只计算一次，而在后面需要时只要简单查一下.n避免重复计算，得到多项式时间的算法.)(22nnnn个不同数中取个不同数中取2个的组合个的组合(i,j), ij i=j时时(i,j)的个数的个数20void MatrixChain(int *p，int n，int *m，int *s) 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

13、(int k = i+1; k j; k+) int t = mik + mk+1j + pi-1*pk*pj; if (t 0) return mij; if (i = j) return 0; int u = LookupChain(i，i) + LookupChain(i+1，j) + pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = LookupChain(i，k) + LookupChain(k+1，j) + pi-1*pk*pj; if (t u) u = t; sij = k; mij = u; return u;27

14、动态规划算法的基本要素动态规划算法的基本要素n最优子结构最优子结构：问题的最优解是由其子问题的最：问题的最优解是由其子问题的最优解所构成的。优解所构成的。n重叠子问题重叠子问题：子问题之间并非相互独立的，而：子问题之间并非相互独立的，而是彼此有重叠的。是彼此有重叠的。最优子结构性质使我们能够以自底向上的方式递归地从子结构的最优解构造出问题的最优解。因为子问题重叠，所以存在着重复计算。这样就可以用填表保存子问题解的方法来提高效率。28备忘录项12 32221 31 21 11 nnmnnmnmmmnmmmm29动态规划算法的基本方法动态规划算法的基本方法n动态规划算法通常可以按以下几个步骤进行：

15、动态规划算法通常可以按以下几个步骤进行：(1)找出最优解的性质，并刻画其结构特征；找出最优解的性质，并刻画其结构特征；(2)递归地定义最优值；递归地定义最优值；(3)以自底向上的方式计算出各子结构的最优值并添以自底向上的方式计算出各子结构的最优值并添入表格中保存；入表格中保存；(4)根据计算最优值时得到的信息，构造最优解。根据计算最优值时得到的信息，构造最优解。u步骤步骤13是动态规划算法的基本步骤。是动态规划算法的基本步骤。u若需要最优解，则必须执行第若需要最优解，则必须执行第4步，为此还需要在步，为此还需要在第第3步中记录构造最优解所必需的信息。步中记录构造最优解所必需的信息。303.3

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

17、列。最长公共子序列最长公共子序列：例如，序列例如，序列X=A，B，C，B，D，A，B，Y=B，D，C，A，B，A的子序列，的子序列，B，C，A是是X与与Y的公共子序列，但不是最长公共子序的公共子序列，但不是最长公共子序列；列；B，C，B，A也是也是X与与Y的公共子序列，但它是的公共子序列，但它是X与与Y的最长公共子序列，因为的最长公共子序列，因为X与与Y没有长度大于没有长度大于4的公共子序列。的公共子序列。32求解的问题求解的问题： 给定给定2个序列个序列: X=x1,x2,xm和和 Y=y1,y2,yn，找出找出X和和Y的最长公共子序列。的最长公共子序列。33u设序列设序列Xm=x1,x2,

18、xm和和Yn=y1,y2,yn的最长公的最长公共子序列为共子序列为Zk=z1,z2,zk ，则，则 (1)若若xm=yn，则，则zk=xm=yn，且，且Zk-1是是Xm-1和和Yn-1的最长的最长公共子序列。公共子序列。 Xi=x1,x2,xi；Yj=y1,y2,yj (2)若若xmyn且且zkxm，则，则Z是是Xm-1和和Yn的最长公共子的最长公共子序列。序列。 (3)若若xmyn且且zkyn，则，则Z是是Xm和和Yn-1的最长公共的最长公共子序列。证明见子序列。证明见P57（二版（二版P49）n2个序列的最长公共子序列包含了它们前缀的最长个序列的最长公共子序列包含了它们前缀的最长公共子序列

19、。公共子序列。n最长公共子序列问题具有最优子结构性质最长公共子序列问题具有最优子结构性质34二二子问题的递归结构子问题的递归结构由最优子结构性质建立子问题最优值的递归关系由最优子结构性质建立子问题最优值的递归关系用用cij记录序列记录序列Xi和和Yj的最长公共子序列的长度，其的最长公共子序列的长度，其中，中， Xi=x1,x2,xi；Yj=y1,y2,yj。当当i=0或或j=0时，空序列是时，空序列是Xi和和Yj的最长公共子序列。的最长公共子序列。故故Cij=0。其他情况下，由最优子结构性质可建立递归关系如下：其他情况下，由最优子结构性质可建立递归关系如下：jijiyxjiyxjijijicj

20、icjicjic; 0,; 0,0, 01,1max1 11035l子问题空间中，共有子问题空间中，共有(mn)个不同的子问题个不同的子问题.l因此，用动态规划算法自底向上地计算最优值能因此，用动态规划算法自底向上地计算最优值能提高算法的效率。提高算法的效率。void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j; for (i = 0; i = m; i+) ci0 = 0; for (i = 0; i = n; i+) c0i = 0; for (i = 1; i = m; i+) for (j = 1; j =c

21、ij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; outcmnendl;3637四、构造最长公共子序列四、构造最长公共子序列LCSLength只是计算出最优值，并未给出最优解，只是计算出最优值，并未给出最优解，然而数组然而数组b可用于快速构造两个序列的最长公共子可用于快速构造两个序列的最长公共子序列：序列：ubij=1时表示时表示Xi和和Yj的最长公共子序列是的最长公共子序列是由由Xi-1和和Yj-1的最长公共子序列加上的最长公共子序列加上xi所得到所得到； ubij=2时表示时表示Xi和和Yj的最长公共子序列的最长公共子序列与与Xi-1和和Yj的最

22、长公共子序列相同的最长公共子序列相同；u bij=3时表示时表示Xi和和Yj的最长公共子序列的最长公共子序列与与Xi和和Yj-1的最长公共子序列相同的最长公共子序列相同。u根据根据b的内容打印出最长公共子序列的内容打印出最长公共子序列38构造最长公共子序列构造最长公共子序列void 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); coutxi; （斜） else if (bij= 2) LCS(i-1，j，x，b); (上) else LCS(i，j-1，x，b);（左）

23、调用调用 LCS(m,n,x,b)，可得，可得39n首先从bm,n开始，沿着其中的箭头所指的方向在数组b中搜索。n当bi,j中遇到“ “时，表示Xi与Yj的最长公共子序列是由Xi-1与Yj-1的最长公共子序列在尾部加上xi得到的子序列；n当bi,j中遇到“时，表示Xi与Yj的最长公共子序列和Xi-1与Yj的最长公共子序列相同；n当bi,j中遇到“时，表示Xi与Yj的最长公共子序列和Xi与Yj-1的最长公共子序列相同。 40n算法lcsLength和lcs中，可进一步将数组b省去。事实上，数组元素cij的值仅由ci-1j-1，ci-1j和cij-1这3个数组元素的值所确定。对于给定的数组元素ci

24、j，可仅借助于c本身确定cij的值是由ci-1j-1，ci-1j和cij-1中哪一个值所确定的。41 p如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算cij时，只用到数组c的第i行和第i-1行。用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n)。42n3.4 最大子段和 （自学）43un个作业1，2，n,要在由机器M1和M2组成的流水线上完成加工。u每个作业加工的顺序都是先在M1上加工，然后在M2上加工。uM1和M2加工作业作业i所需的时间分别为ai和bi。u流水作业调度问题: 要求确定这n个作业的最优加工顺序，

25、使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。44分析：分析：n直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。n在一般情况下，机器M2上会有机器空闲和作业积压两种情况。n设全部作业的集合为N=1，2，n。SN是N的作业子集。n通常，机器M1开始加工S中作业时，机器M2还在加工其它作业，要等时间t后才可利用。n将这种情况下完成S中作业所需的最短时间记为T(S, t)。n流水作业调度问题的最优值为T(N, 0)。453.9.1 最优子结构性质n 设是所给n个流水作业的一个最优调度，它所需的加工时间为 a(1)+T。其中T是在机器是

26、在机器M2的等待时间为的等待时间为b (1)时，安排作业时，安排作业 (2)， (n)所需的时间所需的时间。n记S=N - (1)，则有 T=T(S, b(1)。证明：证明：事实上，由T的定义知TT(S, b(1)(最优)。若TT(S, b(1)，设是作业集S在机器M2的等待时间为b(1)情况下的一个最优调度, 则(1)， (2)， (n)是N的一个调度，且该调度所需的时间为a(1)+T(S,b(1)a(1)+T。这与是N的最优调度矛盾。故TT(S,b(1)。从而T=T(S, b(1)。这就证明了流水作业调度问题具有最优子结构的性质。463.9.2 递归计算最优值由流水作业调度问题的最优子结构

27、性质可知:1(,0)min( ,)ii niTNNTaib (,max,(0, )min)ii SiiT SibT S ttaa一般情况下：因M1完成作业i后，要完成作业i, 在M2上还需时间：max ,max,0iiiiibt aabta47taibit- aimax ,max,0iiiiibt aabta48u设是作业集S在机器M2的等待时间为t时的任一最优调度。若(1)=i, (2)=j, 则由动态规划递归式可得:T(S, t)=ai+ T(S-i, bi+maxt-ai,0)=ai+aj+T(S-i,j,tij)其中：max,max,0maxmax,0,max,0max ,0iijii

28、jjijjijijijijijijijiitbbabtaabbbata abbbat abtaaabaa如果作业i和j满足minbi, ajminbj, ai，则称作业i和j满足Johnson不等式不等式。49 l交换作业交换作业i和和j的加工顺序的加工顺序，得到作业集S的另一调度，它所需的加工时间为: T(S, t)=ai+aj+T(S-i, j,tji) 其中:l当作业i和j满足Johnson不等式minbi, ajminbj,ai时，有max ,jijjjiijjibtbbaat aaa,maxiijiijijijabaataabbt,max,max,max,max,max,max,ma

29、x,maxjjjiiijijjjiiijiijjijijiijjiabaatabaatabaaabaaabaaabaaabab50u因此, tijtji, 故T(S, t) T(S, t).u由此可见:当作业i和j不满足Johnson不等式时，交换它们的加工顺序后，满足Johnson不等式, 且不增加加工时间不增加加工时间。u对于流水作业调度问题，必存在最优调度 ，使得作业(i)和(i+1)满足Johnson不等式, 此时称为满足Johnson法则的调度。u可证：调度满足Johnson法则iff对任意i2n，则算法的复杂性为，则算法的复杂性为(n2n)。算法要求物品的重量算法要求物品的重量wi

30、是整数，而不能为是整数，而不能为实数。实数。610-1背包问题的背包问题的阶跃性阶跃性n函数函数m(i, j)是关于变量是关于变量j的阶梯状单调不减函数：的阶梯状单调不减函数：n由由0-1背包问题的递归式背包问题的递归式m(i, j) =maxm(i+1, j), m(i+1, jwi)+vi jwim(i+1, j) 0jwi可知可知每当每当j增大超过一个物品的重量增大超过一个物品的重量wi时，函数时，函数m(i, j)便有可能增加便有可能增加vi，因而形成了关于变量，因而形成了关于变量j的的阶梯状单调不减函数。阶梯状单调不减函数。n对于对于j为连续，为连续，wi为实数时，为实数时，m(i,

31、 j)依然是梯状依然是梯状单调不减函数。单调不减函数。62阶跃函数阶跃函数m(i, j)的跳跃点的跳跃点n实际上在实际上在m(i, j)的计算中并不需要将的计算中并不需要将j逐渐加逐渐加1。因为因为m(i, j)有阶跃性，而阶梯的长度至少为某个有阶跃性，而阶梯的长度至少为某个wi，即当，即当j增加了某个增加了某个wi， m(i, j)值才会增加相应值才会增加相应vi。这样的点称为这样的点称为函数函数m(i, j)的的跳跃点跳跃点。m(i, j)j0 xicwivi63跳跃点决定了函数跳跃点决定了函数m(i, j)n在在m(i, j)的计算中，只需要计算它的跳跃点的计算中，只需要计算它的跳跃点.

32、n在变量在变量j是连续的情况下，可以对每个确定的是连续的情况下，可以对每个确定的i (1in)，用一个表用一个表Pi来保存来保存m(i, j)的全部跳跃点的全部跳跃点。n对于每一个确定的实数对于每一个确定的实数j，可以通过查表，可以通过查表Pi来确来确定定m(i, j)的值。的值。n由于由于m(i, j)是单调不减的阶梯函数，所以是单调不减的阶梯函数，所以Pi中的中的全部跳跃点的值也是递增排列的。全部跳跃点的值也是递增排列的。64跳跃点的递推关系跳跃点的递推关系n表表Pi 可根据可根据m(i, j)的递归式计算：的递归式计算：n初始时，令初始时，令Pn+1为为(0, 0)。n由递归式由递归式m

33、(i, j) =maxm(i+1, j), m(i+1, jwi)+vi jwim(i+1, j) 0jwi 可知，可知，m(i, j) 的跳跃点集包含于的跳跃点集包含于m(i+1,j)的跳跃点集与的跳跃点集与m(i+1, jwi)+vi 的跳跃点集的并集中的跳跃点集的并集中. n若若(a, b)是是Pi+1中的跳跃点且中的跳跃点且a+wic，则，则(a+wi, b+vi)可可能能是是Pi中的跳跃点。中的跳跃点。65受控跳跃点受控跳跃点n前面产生的跳跃点中有些可能并不是真正的跳前面产生的跳跃点中有些可能并不是真正的跳跃点，而是所谓的跃点，而是所谓的受控跳跃点。n设设(a, b)和和(d, e)

34、都是都是Pi中的跳跃点，若中的跳跃点，若ad且且eb，其情形如下图所示：，其情形如下图所示：m(i, j)jabde显然显然(d, e)不是真正的跳跃点。不是真正的跳跃点。n(d, e)实际上受控于实际上受控于(a, b)，被称为受控跳跃点被称为受控跳跃点。n因此，将前面产生的跳跃点中的受控跳跃点因此，将前面产生的跳跃点中的受控跳跃点删删除除，便可得到，便可得到Pi中的跳跃点。中的跳跃点。n由此便可得到计算表由此便可得到计算表Pi的算法。的算法。66跳跃点的计算跳跃点的计算n初始化：初始化：Pn+1 = (0, 0)； 若已知若已知Pi+1，则有，则有 Pi= Delete-controled

35、(Pi+1(Pi+1 (wi, vi) 其中：其中： Pi+1 (wi, vi) = (a+wi, b+vi) | (a, b)Pi+1 Delete-controled(S)为删去为删去S中的受控跳跃点。中的受控跳跃点。67计算跳跃点的算法计算跳跃点的算法n数组数组P 和和Q 分别存放表分别存放表Pi+1和表和表Pi。n初始化：初始化：P和和Q的首行都为的首行都为0，末行号为，末行号为1。n从从xn开始至开始至x1，对每个物品，对每个物品xi，逐个执行：，逐个执行： 从从P的首行到最末行，对每行的首行到最末行，对每行j逐行执行逐行执行： w = Pj0 + wi； v = Pj1 + vi；

36、 将将Pj0和和Pj1放入放入Q中中； 若若wc，则将，则将w和和v放入放入Q中。中。 将将Q拷贝到拷贝到P，并修改，并修改Q和和P末行号。末行号。68pi=pi+1 qi+1qi+1=pi+1 (wi ,vi ) 删除受控点删除受控点69跳跃点放入跳跃点放入Q中中n跳跃点跳跃点(w, v)放入放入Q中时删去受控跳跃点：中时删去受控跳跃点：n从从Q中的最后行往前对每行中的最后行往前对每行j进行：进行：n 若若Qj0w且且Qj1v，则返回；，则返回；此时跳跃点此时跳跃点(w, v)是受控的。是受控的。n 若若Qj0w且且Qj1v，则将，则将(w, v)插入插入Q中中第第j行的后面，然后返回；行的

37、后面，然后返回；(w, v)的插入可能会引起的插入可能会引起Q中中j行之后的行向后行之后的行向后移动，并要修改移动，并要修改Q的末行号。的末行号。n 若若Qj0w且且Qj1v，则，则 Qj0=w； Qj1 = v；此时此时Qj0和和Qj1是受控的。是受控的。n 若若Qj0w且且Qj1v，则行号，则行号j减一。减一。70一个一个0-10-1背包问题的实例背包问题的实例nn = 5, c = 10, w =2, 2, 6, 5, 4, v = 6, 3, 5, 4, 6 n初始时：P00Q00nn = 5： (w5, v5) = (4, 6)w = P00 + 4 = 4v = P01 + 6 =

38、 6 将(0, 0)放入Q中，因是受控点被删去。将(4, 6)放入Q中，插在了(0, 0)之后。46将Q拷贝到P。结束了P5的计算。46nn = 4： (w4, v4) = (5, 4)w = P00 + 5 = 5v = P01 + 4 = 4 将(0, 0)放入Q中，因是受控点被删去。 将(5, 4)放入Q中，插在了(0, 0)之后。 54w = P10 + 5 = 9v = P11 + 4 = 10 将(4, 6)放入Q中，删去受控点(5, 4)并取代了它的位置。46将(9, 10)放入Q中，放在(4, 6)之后。910将Q拷贝到P。结束了P4的计算。910 nn = 3： (w3, v

39、3) = (6, 5)w = P00 + 6 = 6v = P01 + 5 = 5 将(0, 0)放入Q中，因是受控点被删去。将(6, 5)放入Q中，放在了(0, 0)之后。65 w = P10 + 6 = 10v = P11 + 5 = 11 将(4, 6)放入Q中，删去受控点(6, 5)并取代了它的位置。46 将(10, 11)放入Q中，放在(4, 6)之后。1011 w = P20 + 6 = 15v = P21 + 5 = 15 将(9, 10)放入Q中，放在 (4, 6)之后 ，而(10, 11)挪动了一行 。910 1011 因为w = 15c，所以(15, 15)不再放入Q中 。

40、将Q拷贝到P。结束了P3的计算。1011 nn = 2： (w2, v2) = (2, 3)w = P00 + 2 = 2v = P01 + 3 = 3 将(0, 0)放入Q中，因是受控点被删去。将(2, 3)放入Q中，放在了(0, 0)之后。23 w = P10 + 2 = 6v = P11 + 3 = 9 将(4, 6)放入Q中，放在了(2, 3)之后。46将(6, 9)放入Q中，放在了(4, 6)之后。69w = P20 + 2 = 11v = P21 + 3 = 13 将(9, 10)放入Q中，放在(6, 9)之后。 910因为w = 11c，所以(11, 13)不再Q中。w = P3

41、0 + 2 = 12v = P31 + 3 = 14 将(10, 11)放入Q中，放在(9, 10)之后。1011因为w = 12c，所以(12, 14)不再放入Q中。将Q拷贝到P。结束了P2的计算。2346699101011 nn = 1： (w1, v1) = (2, 6)w = P00 + 2 = 2v = P01 + 6 = 6 将(0, 0)放入Q中，因是受控点被删去。将(2, 6)放入Q中，插在了(0, 0)之后。2 6 w = P10 + 2 = 4v = P11 + 6 = 9 将(2, 3)放入Q中，因是受控点被删去。将(4, 9)放入Q中，放在了(2, 6)之后。4 9 w

42、 = P20 + 2 = 6v = P21 + 6 = 12 将(4, 6)放入Q中，因是受控点被删去。将(6, 12)放入Q中，放在了(4, 9)之后。 6 12 w = P30 + 2 = 8v = P31 + 6 = 15 将(6, 9)放入Q中，因是受控点被删去。将(8, 15)放入Q中，放在(6, 12)之后。8 15 w = P40 + 2 = 11v = P41 + 6 = 16 将(9, 10)放入Q中，因是受控点被删去。因为w = 11c，所以(11, 16)不再放入Q中。w = P50 + 2 = 12v = P51 + 6 = 17 将(10, 11)放入Q中，因是受控点

43、被删去。因为w = 12c，所以(12, 17)不再放入Q中。将将Q拷贝到拷贝到P，结束了，结束了P1的计算。的计算。2 6 4 9 6 12 8 15 71n构造其解：n由P1=(0,0),(2,6),(4,9),(6,12),(8,15)知m(1,10)=15n由P2=(0,0),(2,3),(4,6),(6,9),(9,10), (10,11) 知m(2,10)=11, x1=1, m(2,8)=9n由P3=(0,0),(4,6),(9,10), (10,11) 知m(3,8)=6, x2=1, m(3,6)=6n由P4=(0,0),(4,6),(9,10) 知m(4,6)=6, x3=

44、0n由P5=(0,0),(4,6) 知 m(5,6)=6, x4=0n而由m(6,6)=0知, x5=1n 因此，本例中第一、二、五个物品装包。 72計算跳跃点的时间复杂性計算跳跃点的时间复杂性n计算计算qi+1 Pi+1 (wi, vi) 需要需要O(| Pi+1|)的时的时间。间。n然后再与然后再与Pi+1合并和删去受控跳跃点也需要合并和删去受控跳跃点也需要O(| Pi+1|)的时间。的时间。n但是但是Pi中的跳跃点只是中的跳跃点只是x1, x2, , xn的的0-1赋值，赋值，因而其个数不会超过因而其个数不会超过2ni+1。n因此，计算跳跃点集所花费的时间为：因此，计算跳跃点集所花费的时

45、间为： n nO(|Pi+1|) = O(2ni) = O(2n) i=2 i=2n所以改进后的算法复杂性为所以改进后的算法复杂性为O(minnc, 2n)。Down73动态规划法总结动态规划法总结n与分治法相比，相同之处是也将原问题分解为若与分治法相比，相同之处是也将原问题分解为若干子问题，再递归求解；不同之处是所分解的子干子问题，再递归求解；不同之处是所分解的子问题彼此并不独立，而是互有问题彼此并不独立，而是互有重叠重叠。n基本思想是基本思想是造表记录已解的子问题造表记录已解的子问题，再次遇到时，再次遇到时仅查表即可，避免了重复计算，提高效率。仅查表即可，避免了重复计算，提高效率。n通常用于求解具有最优性质的问题，而且其子问通常用于求解具有最优性质的问题，而且其子问题也具有最优性质题也具有最优性质(最优子结构性质最优子结构性质)。n实现方法通常为自底向上的递归形式，但也可以实现方法通常为自底向上的递归形式，但也可以采用自上而下的形式采用自上而下的形式(