算法设计-第3章

1、12 学习要点学习要点:理解动态规划算法的概念。掌握动态规划算法的基本要素（1）最优子结构性质（2）重叠子问题性质掌握设计动态规划算法的步骤。(1)找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。3通过应用范例学习动态规划算法设计策略。（1）矩阵连乘问题；（2）最长公共子序列；（3）最大子段和（4）凸多边形最优三角剖分；（5）多边形游戏； （6）图像压缩；（7）电路布线；（8）流水作业调度；（9）背包问题；（10）最优二叉搜索树。4n动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问

2、题nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=5nT(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)n先求子问题的解，然后从这些子问题的解得到原问题的解。6n但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。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/4)T(n/4)

3、T(n/4)T(n/4) T(n/4)T(n)7n如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。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/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n)8n动态规划方法常用来求解最优化问题。n其思想是：问题的最优解如果可以由子问题的最优解推导得到，则可以先求解子问题的最优解，再构造原问题的最优解；若子问题有较多的重复出现，则可以自底向上，从最终子问题向原问题逐步求解。9n找出最优解的性质，并刻划其结构特征。n递归地定

4、义最优值。n以自底向上的方式计算出最优值。n根据计算最优值时得到的信息，构造最优解。10n给定n个矩阵 ， 其中 与 是可乘的， 。考察这n个矩阵的连乘积 n由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。n若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积,.,21nAAAiA1iA1,.,2 , 1ninAAA.21111.设Apq,Aqr两矩阵相乘，普通乘法的次数为pqr2.加括号对乘法次数的影响 如：A(10100)B(1005)C(550) (AB)C

5、): 7500次 (A(BC): 75000次例：例： 设有四个矩阵设有四个矩阵A,B,C,DA,B,C,D，它们的维数分别是：，它们的维数分别是：A=50A=501010，B=10B=104040，C=40C=403030，D=30D=305 5总共有五种完全加括号的方式：总共有五种完全加括号的方式：(A(BC)D) (A(B(CD) (AB)(CD) (AB)C)D) (A(BC)D) (A(B(CD) (AB)(CD) (AB)C)D) (A(BC)D)(A(BC)D)其数乘次数分别为：其数乘次数分别为：16000, 10500, 36000, 87500, 16000, 10500,

6、36000, 87500, 345003450012（1）单个矩阵是完全加括号的；（2）矩阵连乘积 是完全加括号的，则 可 表示为2个完全加括号的矩阵连乘积 和 的乘积并加括号，即 AABC)(BCAu完全加括号的矩阵连乘积可递归地定义为：13 问题描述： 给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1，2，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。u穷举法穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。 算法复杂度分析：算法复杂度分析：l对于n个矩阵的连乘积，设其不

7、同的计算次序为P(n)。l由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1An)可以得到关于P(n)的递推式如下：14 2/311/42111111nnnnnCnCnPnknPkPnnPnnk，其中，l也就是说，P(n)是随n的增长成指数增长的。因此，穷举法不是一个有效算法.),)(1679648621430429nP15u下面我们考虑用动态规划动态规划求解。p预处理：将矩阵连乘积 简记为Ai:j ，这里ij jiiAAA.1考察计算Ai:j的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，ikj，则其相应完全加括号方式

8、为).)(.(211jkkkiiAAAAAA计算量：Ai:k的计算量加上Ak+1:j的计算量，再加上Ai:k和Ak+1:j相乘的计算量16n特征：计算Ai:j的最优次序所包含的计算矩阵子链 Ai:k和Ak+1:j的次序也是最优的。n矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。17n设计算Ai:j，1ijn，所需要的最少数乘次数mi,j，则原问题的最优值为m1,n n当i=j时，Ai:j=Ai，因此，mi,i=0，i=1,2,nn当ij时， 根据最优子结构性质，计算mij。n若计算Ai:

9、j的最优次序在Ak和Ak+1之间断开，i=kj,则mij=mik+mk+1j+pi-1pkpj 由于不知道在那里断开，所以k的位置未定， 因此k是这j-i个位置中使计算量达到最小的哪个位置。但但 的位置只有的位置只有 种种可能可能kij ).)(.(211jkkkiiAAAAAA18l取得的k为Ai:j最优次序中的断开位置，并记录到表sij中，即sij k l 注：mij实际是子问题最优解的解值，保存下来避免重复计算。jipppjkmkimjijimjki, 1,min0,1jki所以， mi,j 可以递归地定义为：计算量：Ai:k的计算量加上Ak+1:j的计算量，再加上Ai:k和Ak+1:j

10、相乘的计算量19n递归求解最优解的值 计算m14过程如下： 如A3:4被计算了2次，保存下来可以节省许多时间20n自底向上记忆化方式求解mij - 计算方向： j m11, m12, m13, , m1n m22, m23, , m2n i mn-1n-1, mn-1n mnn - 注：也可以自顶向下计算(含重复计算)，这样效率较低(为(2n)。DP算法在求每个mij时，如果每计算就递归，否则就查表。21n对于1ijn不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有n由此可见，在递归计算时，许多子问题被重复计算多次许多子问题被重复计算多次。这也是该问题可用动态规划算法求

11、解的又一显著特征。n用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法)(22nnn22基本思路：1.计算最优值算法MatrixChain（），建立两张表m和s(用两维数组表示），m存放矩阵相乘的最小运算量，主对角线上的值为0，依次求2个矩阵、3个矩阵，直到n个矩阵相乘的最小运算量，其中每次矩阵相乘的最小运算量都在上一次矩阵相乘的最小运算量基础上求得，最后一次求得的值即为n个矩阵相乘的最小运算量；s存储最优断开位置。2.输出矩阵结合方式算法Tr

12、aceback（）：矩阵结合即是给矩阵加括号，打印出矩阵结合方式，由递归过程Traceback（）完成。分三种情况：（1）只有一个矩阵，则只需打印出A；（2）有两个矩阵，则需打印出(A1A2);（3）对于矩阵数目大于2，则应该调用递归过程Traceback（）两次，构造出最优加括号方式。23void MatrixChain(int *p，int n，int *m，int *s) /计算mij所需的最少数乘次数,并记录断开位置sij for (int i = 1; i = n; i+) mii = 0; /单个矩阵相乘,所需数乘次数为0 for (int r = 2; r = n; r+) fo

13、r (int i = 1; i = n - r+1; i+) int j=i+r-1; /首先在i断开，即(Ai*(Ai+1.Aj) mij = mi+1j+ pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) /然后在k（从i+1开始遍历到j-1）断开，即（Ai.Ak)*（Ak+1.Aj） int t = mik + mk+1j + pi-1*pk*pj; if (t mij) /找到更好的断开方法 mij = t; /记录最少数乘次数 sij = k; /记录断开位置 算法描述：算法描述：24示例A1A2A3A4A5A630 3535 1515

14、55 1010 2020 25113752010350437555427125205351000262554 3213000201535250005322min52541531521pppmmpppmmpppmmm25算法复杂度分析：算法复杂度分析：算法matrixChain的主要计算量取决于算法中对r，i和k的3重循环。循环体内的计算量为O(1)，而3重循环的总次数为O(n3)。因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。26 由算法matrixChain中中sij = k 知，计算矩阵链Ai:j的最优加括号括号方式应为（Ai:k）（Ak+1:j）。故从s1n 记录

15、的信息知，计算A1:n的最优加括号括号方式为（A1: s1n ）（）（ As1n+ 1:n）。）。而A1: s1n的最优加括号括号方式为（A1: s1 s1n ）（）（ As1 s1n +1：s1 s1n ）。由此可确定A1:n的最优完全加括号括号方式，即构造出问题的一个 算法Ttanceback按算法matrixChain递归递归计算出断点矩阵s指示的加括号括号方式输出计算Aij 的计算次序。2728void Traceback(int i，int j，int *s) /sij记录了断开的位置，即计算Ai:j的加括号方式为Ai:sij)*(Asij+1:j) if (i = j) retur

16、n; Traceback (i, sij, s); /递归打印Ai:sij的加括号方式 Traceback (sij+1, j, s); /递归打印Asij+1:j的加括号方式 cout “Multiply A” i “,” sij; cout “ and A “ (sij+1) “,” j endl;29n例：例： A1:6对应s16 =3，k=3 （A1:3 ）（A4:6）而A1:3最优加括号括号方式为 （A1: s1：3 ）（ As1：3 +1：s1：6）即A1 A 2：3 同理讨论A4:6。计算计算A16 的最优计算次序为的最优计算次序为（ （ A1（A2 A3 ） ） （ （ A4

17、A5 ） A6 ） ） 。303.2 动态规划算法的基本要素n从计算矩阵连乘积最优计算次序的动态规划算法可以看出，该算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和子问题重叠性质。从一般意义上讲，问题的这两个重要性质是该问题可以用动态规划算法求解的基本要素。本节着重介绍：q最优子结构q重叠子问题q备忘录方法n此外，本节最后对动态规划算法与备忘录方法的适用条件作了简单介绍。31l矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质最优子结构性质。l在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再

18、设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。 l利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。注意：同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）32l递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质子问题的重叠性质。l动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。 l通常不同的子问题个数随问题的大

19、小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。 33void RecurMatrixChain (int i，int j) if (i=j) return 0; int u= RecurMatrixChain( i,i)+ RecurMatrixChain( i+1,j)+pi-1*pi*pj; sij= i; for (int k= i+1; kj;k+) int t= RecurMatrixChain( i,k)+ RecurMatrixChain( k+1,j)+pi-1*pk*pj; if (tu) u=t;sij=k; return u;3435l备忘录

20、方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。Int MemoizedMatrixChain(int n,int *m,int *s) for (int i=1;i=n;i+) for (int j= i;j 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 = LookupChai

21、n(i，k) + LookupChain(k+1，j) + pi-1*pk*pj; if (t u) u = t; sij = k; mij = u; return u;算法复杂性：算法复杂性：T(n)=O(n3)37关于动态规划算法和备忘录方法的适用条件n综上所述，矩阵连乘积的最优计算次序问题可用自顶向下的备忘录方法或自底向上的动态规划算法在O(n3)计算时间内求解。n这两个算法都利用了子问题重叠性质。总共有(n2)个不同的子问题，对每个子问题两种算法都只解一次并记录答案。当再次遇到该子问题时，简单地取用已得到的答案，节省了计算量，提高了算法的效率。n适用条件：一般来说，当一个问题的所有子问

22、题都至少要解一次时，用动态规划算法比用备忘录方法好。此时，动态规划算法没有任何多余的计算，还可以利用其规则的表格存取方式来减少在动态规划算法中的计算时间和空间需求。当子问题空间中部分子问题可以不必求解时，易用备忘录方法则较为有利，因为从其控制结构可以看出，该方法只解那些确实需要求解的子问题。38n注注：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而非一种特殊算法，故没有一个标准的数字表达式和明确定义的一组规则，必须对具体问题具体分析处理。所以，除对基本概念，方法，正确理解外，应以丰富的想象力去建立模型（递推关系式），用创造性的技巧去求解问题。39概述：l一个给定序列的子序列是在该序

23、列中删去若干元素后得到的序列。l若给定序列X=x1,x2,xm，则另一序列Z=z1,z2,zk，是X的子序列是指存在一个严格递增下标序列i1,i2,ik使得对于所有j=1,2,k有：zj=xij。l例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相应的递增下标序列为2，3，5，7。40序列序列B,C,A是是X和和Y 的公共子序列但不是最长的。的公共子序列但不是最长的。X和和Y的最长公共子序列为：的最长公共子序列为：BCBA、BCAB。例：例：X=ABCBDAB，Y=BDCABA问题： 给定2个序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最长公共子序列。

24、 最长公共子序列不唯一。最长公共子序列不唯一。l给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。公共子序列。41 对X的所有子序列，检查是否也是Y的子序列，从而确定它是否为X何y的公共子序列。 并且在检查过程中记录最长的公共子序列。 X的所有子序列检查过后即可求出X和Y的最长公共子序列。 X的每个子序列相应于下标集 1，2，m的一个子集。因此共有2m个不同子序列。所以时间复杂度O( 2m) 42设序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列为Z=z1,z2,zk ，则可推论：p(1)若xm=yn，则zk=xm=yn，且zk-1是X

25、m-1和Yn-1的最长公共子序列。p(2)若xmyn且zkxm，则Z是Xm-1和Y的最长公共子序列。p(3)若xmyn且zkyn，则Z是X和Yn-1的最长公共子序列。l分析：分析：对序列X=x1,x2,xm，定义X0= ，X1=x1, X2=x1,x2, ，Xm= x1,x2,xm定义Y=y1,y2,yn，定义Y0= ，Y1=y1,Y2=y1,y2,，Yn= y1,y2,yn43 由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质最优子结构性质。 x1x2x3x4xm-1xmy1y2y3yn-1ynz1z2zk-1zk44n递归

26、解法q问题形式：求X=x1,x2,，xm和Y=y1,y2,，yn的最长公共子序列；q递归规则：若xm=yn，则求Xm-1和Yn-1的最长公共子序列Zk-1,然后在其尾部加上xm(=yn)即可得X和Y的最长公共子序列，即Zk-1+xm ； 否则,当xmyn 时，求Xm-1和Y的最长公共子序列Z1( zkxm );求X和Yn-1的最长公共子序列Z2 (zkYn )；比较Z1和Z2，长度较长的序列即结果；q终结条件：若X或Y为空序列，则Z为空序列；45由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用cij记录序列Xi和Yj的最长公共子序列的长度。其中， Xi=x1,x2,xi；Yj

27、=y1,y2,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时Cij=0。其它情况下，由最优子结构性质可建立递归关系如下：jijiyxjiyxjijijicjicjicjic; 0,; 0,0, 01,1max1 11046(m,n)(m-1,n-1)|(m,n-1),(m-1,n)(m-2,n-2)|(m-1,n-2),(m-2,n-1)(m-1,n-2)|(m,n-2),(m-1,n-1)(m-2,n-1)|(m-1,n-1),(m-2,n)最长公共子序列47n自底向上构造最优值q求解X1：m和Y1：n的最长公共子序列，记为(Xm,Yn)引入辅助向量c0:m0:n, 和

28、b1:m1:n ： c0:m0:n记录子问题的最优值，cij表示(Xi,Yj)的长度，i或j为0表示X或Y为空序列； b1:m1:n记录子问题的解，bij表示(Xi,Yj)是由哪一个子问题的解得到的，约定：约定：若是由(Xi-1,Yj-1)的解得到的，bij记为1；若是由(Xi-1,Yj)的解得到的，bij记为2；若是由(Xi,Yj-1)的解得到的，bij记为3。由于在所考虑的子问题空间中，总共有(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。 48n自底向上构造最优值q从空序列开始，逐步计算子问题：初始化ci0 = 0; c0i = 0;对比X和Y的全部字符

29、对，i=1.m, j=1.n： 若Xi=Yj，则 由递归规则：cij = ci-1j-1+1cij = ci-1j-1+1； 记录bij = 1bij = 1; 否则 选子问题中的最小值作为当前问题的最优值，即： cij = max ci-1jcij = max ci-1j，cij-1 cij-1 并分别记录bij=2bij=2 或 bij=3bij=3;49void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j; for (i = 1; i = m; i+) ci0 = 0; for (i = 1; i = n; i

30、+) c0i = 0; for (i = 1; i = m; i+) for (j = 1; j =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; 50n构造最优解q由计算最优值时得到的b1：m1：n，可以递归地得到最优解，递归过程如下：q问题形式：X1：i，Y1：jq递归规则：q首先从bmn开始，依其值在数组b中搜索，若bij=1（xi=yj的情况），则：解为：X1i-1，Y1j-1的解 + xi 若bij=2（ X1i-1，Y1j的最优解），则解为： X1i-1，Y1j的解若bij=3（ X1i，Y1j-1的最优解），则解为： X1i，Y1j

31、-1的解q终结条件：i或j为0时，解为空序列；51void 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);520 06 A6 A0 05 B5 B0 07 B7 B0 05 D5 D0 04 B4 B0 03 C3 C0 02 B2 B0 01 A1 A0 00 00 00 00 00 00 -0 -6 A6 A4 A4 A3 C3 C2 D2 D1

32、 B1 B0 -0 -XYij0 01 11 10 00 01 11 11 11 11 12 22 22 22 22 22 21 12 22 23 32 23 33 32 23 34 41 11 11 11 12 22 23 34 44 42 21 12 23 32 21 1对b递归推导得解：BCBAAB3 3CB例：例：X=ABCBDABX=ABCBDAB，Y=BDCABAY=BDCABA计算规则：若Xi=Yj，则Ci,j=Ci-1,j-1+1，bi,j=1；否则，若Ci-1,j较大，则Ci,j=Ci-1,j，bi,j=2；否则，Ci,j=Ci,j-1，bi,j=3为便于观察，将b=1标为斜

33、箭头，2标为上箭头，3标为左箭头53 在算法lcsLength和lcs中，可进一步将数组b省去。事实上，数组元素cij的值仅由ci-1j-1，ci-1j和cij-1这3个数组元素的值所确定。对于给定的数组元素cij，可以不借助于数组b而仅借助于c本身在O(1)时间内确定cij的值是由ci-1j-1，ci-1j和cij-1中哪一个值所确定的。 如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算cij时，只用到数组c的第i行和第i-1行。因此，用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n)。543.4 最大子段和n问

34、题描述n简单算法：T(n)=O(n2) n分治算法：T(n)=O(nlogn) n动态规划算法：T(n)=O(n)55n问题描述：问题描述：p 给定由给定由n n个整数（包含负整数）组成的序列个整数（包含负整数）组成的序列a a1 1, ,a a2 2,.,.,a an n，求该求该序列子段和的最大值。当所有整数均为负值时定义其最大子段序列子段和的最大值。当所有整数均为负值时定义其最大子段和为和为0 0。p 依此定义，所求的最优值为：依此定义，所求的最优值为：p n例如，当例如，当( (a a1 1, ,a a2 2, , a a3 3, , a a4 4, , a a5 5, ,a a6 6

35、)=(-2,11,-4,13,-5,-2)=(-2,11,-4,13,-5,-2)时，最大子时，最大子段和为：段和为：p jikknjia1max, 0max201341142kka561. 简单算法int MaxSubSum1(int n, int a, int & besti, int & bestj) /数组a存储ai，返回最大子段和，保存起止位置到Besti,Bbestj中 int sum=0; for(int i=1; i=n; i+) for(int j=i; j=n; j+) /i、j是子串的起始位置 int thissum=0; for(int k=i; ksu

36、m) / 更新目前为止最大子串长度和起始位置 sum=thissum; besti=i; bestj=j; return sum; 注: 原算法：T(n)=O(n3); /可以改进，省略此循环57n由于有：n算法可作如下改进：int MaxSum(int n, a, &besti, &bestj)int sum=0;for(i=1;i=n;i+)int thissum=0;for(j=i;jsum)sum=thissum;besti=i;bestj=j;n改进后的算法复杂性为O(n2) 。1jikkjjikkaaa58nnkkninnikknijikkasasnjnniaC12

37、1222211maxmax12,21 ,.jikknjnnia12,21 ,2. 分治方法求解n从问题的解的结构可以看出，它适合于用分治策略求解：q如果将所给的序列a1:n分为长度相等的两段a1:n/2和an/2+1:n，分别求出这两段的最大子段和，则a1:n的最大子段和有三种情形：A.a1:n的最大子段和与a1:n/2的最大子段和相同；B.a1:n的最大子段和与an/2+1:n的最大子段和相同；C. a1:n的最大子段和为qA、B这两种情形可递归求得。对于情形C，容易看出，an/2与an/2+1在最优子序列中。因此，我们可以在a1:n/2和an/2+1:n中分别计算出如下的s1和s2。则s1

38、+s2即为出现情形C时的最优值。q从而设计出下面所示的分治算法。59最大子段和: 分治算法（续）n算法算法 int MaxSubSum(int a, int left, int right) /返回最大子段和返回最大子段和 int sum=0; if(left=right) sum=aleft0?aleft:0; else int center=(left+right)/2; int leftsum= MaxSubSum2(a, left,center); int rightsum= MaxSubSum2(a, center+1, right); int s1=0; int leftmidsu

39、m=0; for(int i=center; i=left; i-) leftmidsum += ai; if(leftmidsums1) s1=leftmidsum; int s2=0; int rightmidsum=0; for(int i=center+1; is2) s2=rightmidsum; int sum=s1+s2; if(sumleftsum) sum=leftsum; if(sum0时bj=bj-1+aj，否则bj=aj。由此可得计算bj的动态规划递归式bj=maxbj-1+aj ，aj，1jn。n据此，可设计出求最大子段和的动态规划算法如下：jnjjikkjinjjk

40、knjijikkjijbaanjab111111maxmaxmaxmax1max为，则所求的最大子段和，若记考虑所有下标以j结束的最大子段和bj61最大子段和: 动态规划算法（续）n算法qint MaxSum(int n, int a)qq int sum=0, b=0; /sum存储当前最大的bj, b存储bjq for(int j=1; j0) b+= aj;q else b=ai; /一旦某个区段和为负，则从下一个位置累和q if(bsum) sum=b;q q return sum;q n运行时间：T(n)=O(n)n思考题 如果要记录最大子段的区间，如何修改程序？62j2j1ji2i

41、1iaij4. 最大子段和问题与动态规划算法的推广（1）最大子矩阵和问题： 给定一个m行n列的整数矩阵A，试求矩阵A的一个子矩阵，使其个元素之和最大。最大子矩阵和问题是最大字段和问题向二维的推广。用二维数组a1:m1:n表示给定的m行n列的矩阵。子数组ai1:i2j1:j2表示左上角和右下角行列坐标分别为（i1,j1)和（i2,j2)的子矩阵，其各元素之和记为： s(i1,i2,j1,j2)=最大子矩阵和问题的最优值为max s(i1,i2,j1,j2). 1i1 i2 m 1 j1 j2 n 如果用直接枚举方法求出最大矩阵问题，需要O(m2n2)时间。63注意到max s(i1,i2,j1,

42、j2).= max max s(i1,i2,j1,j2)=max t(i1,i2) 1i1 i2 m 1i1 i2 m 1 j1 j2 n 1i1 i2 m 1 j1 j2 n 式中，t(i1,i2)= max s(i1,i2,j1,j2)= max 1 j1 j2 n 1 j1 j2 n i2i1ij2j1jaij设bj= ，则t(i1,i2)=max 1 j1 j2 ni2i1iaiji2i1ibj这正是一维情形的最大字段和问题。，由此，借助最大子段和问题的动态规划算法，可设计出解最大子矩阵和问题的动态规划算法。64n算法qint MaxSum2(int n, int a)qq int s

43、um=0；q int * b=new intn+1; /sum存储当前最大的bj, b存储bjq for(int i=1; i=m; i+) q for (int k=1;k=n;k+) bk = 0;q for (int j=i ;j=m;j+) q for (int k=1;ksum) sum=max;q q q return sum;q n运行时间：T(n)=O(m2n)0-10-1背包问题背包问题65用多边形顶点的逆时针序列表示凸多边形，即P=v0,v1,vn-1表示具有n条边的凸多边形。若vi与vj是多边形上不相邻的2个顶点，则线段vivj称为多边形的一条弦。弦将多边形分割成2个多边

44、形vi,vi+1,vj和vj,vj+1,vi。多边形的三角剖分多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合T。给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小。 66一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。例如，完全加括号的矩阵连乘积(A1(A2A3)(A4(A5A6)所相应的语法树如图 (a)所示。凸多边形v0,v1,vn-1的三角剖分也可以用语法树表示。例如，图 (b)中凸多边形的三角剖分可用图 (a)所示的语法树表示。 矩阵连乘积中的每个矩阵Ai对应于凸(n

45、+1)边形中的一条边vi-1vi。三角剖分中的一条弦vivj，ij，对应于矩阵连乘积Ai+1:j。67凸多边形的最优三角剖分问题有最优子结构性质。事实上，若凸(n+1)边形P=v0,v1,vn-1的最优三角剖分T包含三角形v0vkvn，1kn-1，则T的权为3个部分权的和：三角形v0vkvn的权，子多边形v0,v1,vk和vk,vk+1,vn的权之和。可以断言，由T所确定的这2个子多边形的三角剖分也是最优的。因为若有v0,v1,vk或vk,vk+1,vn的更小权的三角剖分将导致T不是最优三角剖分的矛盾。 68定义tij，1in时，顶点i+s实际编号为(i+s)mod n。按上述递推式计算出的m

46、i,n,1即为首次删去第i条边后得到的最大得分。773.算法描述算法描述nvoid minMax(int n,int s,int j,int &minf,int &maxf)nn int e4;n int a=mis0, b=mis1, r=(i+s-1)%n+1;n int c=mrj-s0, d=mrj-s1;n if(opr=+) minf=a+c; maxf=b+d; n elsen n e1=a*c; e2=a*d; e3=b*c; e4=b*d;n minf=e1; maxf=e1;n for(int r=2;rer) minf=er;n if(maxfer) ma

47、xf=er;n n n 78nint polyMax(int n)nint minf,maxf;n for(int j=2;j=n;j+)n for(int i=1;i=n;i+)n for(int s=1;sminf) mij0=minf;n if(mij1maxf) mij1=maxf;n n int temp=m1n1;n for(int i=2;i=n;i+)n if(tempmin1) temp=min1;n return temp;n 79图象的变位压缩存储格式将所给的象素点序列p1,p2,pn,0pi255分割成m个连续段S1,S2,Sm。第i个象素段Si中(1im)，有li个象

48、素,且该段中每个象素都只用bi位表示。设 则第i个象素段Si为设 ，则hibi8。因此需要用3位表示bi,如果限制1li255，则需要用8位表示li。因此，第i个象素段所需的存储空间为li*bi+11位。按此格式存储象素序列p1,p2,pn，需要 位的存储空间。 图象压缩问题要求确定象素序列p1,p2,pn的最优分段，使得依此分段所需的存储空间最少。每个分段的长度不超过256位。11ikklit,1ilititippS1maxlog1kilitkitiphmibilmi11*180设li，bi，是p1,p2,pn的最优分段。显而易见，l1，b1是p1,pl1的最优分段，且li，bi，是pl1+

49、1,pn的最优分段。即图象压缩问题满足最优子结构性质。设si，1in，是象素序列p1,pn的最优分段所需的存储位数。由最优子结构性质易知：其中11), 1max(b*min256,min1ikikkisisik1maxlog),bmax(kjkipji算法复杂度分析：算法复杂度分析：由于算法compress中对k的循环次数不超这256，故对每一个确定的i，可在时间O(1)内完成的计算。因此整个算法所需的计算时间为O(n)。 81在一块电路板的上、下2端分别有n个接线柱。根据电路设计，要求用导线(i,(i)将上端接线柱与下端接线柱相连，如图所示。其中(i)是1,2,n的一个排列。导线(i,(i)

50、称为该电路板上的第i条连线。对于任何1i(j)。电路布线问题要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。换句话说，该问题要求确定导线集Nets=(i,(i),1in的最大不相交子集。 82记 。N(i,j)的最大不相交子集为MNS(i,j)。Size(i,j)=|MNS(i,j)|。(1)当i=1时，(2)当i1时，2.1 j(i)。此时， 。故在这种情况下，N(i,j)=N(i-1,j)，从而Size(i,j)=Size(i-1,j)。2.2 j(i)，(i,(i)MNS(i,j) 。 则对任意(t,(t) MNS(i,j)有ti且(t)(i)。在这种情况下MNS(i,j)-

51、(i,(i)是N(i-1,(i)-1)的最大不相交子集。 2.3 若 ，则对任意(t,(t) MNS(i,j)有 t1时) 1 (1) 1 (0), 1 (jjjSize)()(1) 1)(, 1(), 1(max), 1(),(ijijiiSizejiSizejiSizejiSize83n个作业1，2，n要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。分

52、析：分析：直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。在一般情况下，机器M2上会有机器空闲和作业积压2种情况。设全部作业的集合为N=1，2，n。SN是N的作业子集。在一般情况下，机器M1开始加工S中作业时，机器M2还在加工其它作业，要等时间t后才可利用。将这种情况下完成S中作业所需的最短时间记为T(S,t)。流水作业调度问题的最优值为T(N,0)。84设是所给n个流水作业的一个最优调度，它所需的加工时间为 a(1)+T。其中T是在机器M2的等待时间为b(1)时，安排作业(2)，(n)所需的时间。记S=N-(1)，则有T=T(S,b(1)。证明：证明：事实上，由T的定

53、义知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)。这就证明了流水作业调度问题具有最优子结构的性质。由流水作业调度问题的最优子结构性质可知，),(min)0 ,(1iinibiNTaNT)0 ,max,(min),(iiiSiatbiSTatST85对递归式的深入分析表明，算法可进一步得到简化。设是作业集S在机器M2的等待时间为t时的任一最优调度。若(1)=i,

54、(2)=j。则由动态规划递归式可得:T(S,t)=ai+T(S-i,bi+maxt-ai,0)=ai+aj+T(S-i,j,tij)其中，,max0 ,max,0 ,maxmax0 ,0 ,maxmaxiijiijijijijijijijijjiijijabaataabbbaatabbbaatabbaatbbt如果作业i和j满足minbi,ajminbj,ai，则称作业i和j满足JohnsonJohnson不等式不等式。86交换作业i和作业j的加工顺序，得到作业集S的另一调度，它所需的加工时间为T(S,t)=ai+aj+T(S-i,j,tji)其中，当作业i和j满足Johnson不等式时，有由

55、此可见当作业i和作业j不满足Johnson不等式时，交换它们的加工顺序后，不增加加工时间。对于流水作业调度问题，必存在最优调度 ，使得作业(i)和(i+1)满足Johnson不等式。进一步还可以证明，调度满足Johnson法则当且仅当对任意i0，wi0，vi0， 1i n，要求找出一个n元0-1向量（x1,x2,，xn)，xi0，1， 1i n，使得 c，而且 达到最大。niiixw1niiixv189因此，0-1背包问题是一个特殊的整数规划问题。使目标函数最大求).,(1nllxxxnixCxwiniii1,1 , 01niiixv1max抽象之后背包问题转换为找到一个最优的数组，x1，x2

56、，.,xn的0-1序列。 90举例：w=(w1,w2,w3)=(2,3,4), v=(v1,v2,v3)=(1,2,5), n=3, c=6, 求Knap(w,v,3,6) 取x=(1,0,1)时， 用穷举法求解，思想：枚举所有可能的情况，找出其中的最大值。用n位二进制数表示N件物品的选取情况，例如：n=3,100表示选取了第一件物品，000表示为选取任何物品。所以时间复杂度为O(2n)niiixv16150211最大91 /获取背包内物品的最大值 int GetBestValue() const int bestValue=0; /背包最大价值 int currentValue =0; /当

57、前背包中物品的价值 int currentWeight =0; /当前背包中物品的重量 const unsigned int max = 2 m_num; /2的N次方 /枚举所有可能的解 for(unsigned int i =0; i=1; +j; /保存最优解 if(currentWeight =m_c & bestValue wi, 就只要做出选择wi和不选择wi情况下，哪种更能使背包的总价值更大： m(i,j)=max m(i+1,j),m(i+1,j-wi)+vi(注意这是个递归式) (2) 如果j= wn)； m(n,j)=0 (0=j wn) 最终的结果：m(1,C)9

58、70-1背包问题: 递归关系 n递归式如下：)4()3(00),(), 1(1), 1(0);, 1(),(, 0)2(0), 1() 1 (), 1(), 1(),(nnniiiiiiiiiiiwjwjvjnmvwjimxjimxwjjimjimxwjwjjimaxwjvwjimjimmaxjim临界条件：最优子结构为时，取为时，取时，当只有时，当说明：不取物品i取物品i98iiiiwjwjjimvwjimjimjim0), 1(), 1(), 1(max),(nnnwjwjvjnm00),(递归式如下：993. 0-1背包问题: 算法 void Knapsack(float v, int

59、w, int c, int n, float m) /输出m1c int jMax=min(wn-1, c); /初始化mnj ，表示当第n个物体的体积大于背包体积时，就不选择；当第n个物体的体积小于背包体积时，选择 for(int j=0; j=jMax; j+) mnj=0; / 0jwn, (4)式，表示将第n个物体放入体积为j的背包中，由于其体积小于物体n的体积，所以不选择 for(int j=wn; j1; i-) /第i个物体的选择/i1表示对i=1不处理，因为i=1时只需求m1c jMax=min(wi-1, c); 100for(int j=0; j=jMax; j+) /0j

60、wi, (2)式/*当体积小于第i个物体的体积时，不选择第i个物体*/ mij=mi+1j; for(int j=wi; j=c; j+) /j wi, (1)式 mij=max(mi+1j, mi+1j-wi+vi); /*当体积大于第i个物体的体积时，需要进行判断是否选择第i个物体，判断的依据是如果不放第i件物品，那么问题就转化为“前n-i+1(因为这里采用的是从第n个物体开始的，所以第i个物体前面有n-i+1件物体)件物品放入容量为j的背包中”，其价值为mi+1j；如果放第i件物品，那么问题就转化为“前n-i+1件物品放入剩下的容量为j-wi的背包中”，此时能获得的最大价值就是mi+1j-wi再加上通过放入第i件物品获得的价值vi。*/