第三章 动态规划(1)

1、第三章第三章 动态规划动态规划动态规划算法与分治法类似，其基本思想也是将动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。待求解问题分解成若干个子问题。nT(n/2)T(n/2)T(n/2)T(n/2)T(n)= 但是经分解得到的子问题往往不是互相独立的。不但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。时，有些子问题被重复计算了许多次。算法总体思想算法总体思想n 采用自底向上的求解方式能够保证每个字问题只被采用自底向上的求解方式能够保证每个字问题

2、只被求解一次。求解一次。n 或者，采用自上而下的方式求解时，保存已解决的或者，采用自上而下的方式求解时，保存已解决的子问题的答案，而在需要时再找出已求得的答案，就子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。可以避免大量重复计算，从而得到多项式时间算法。n 找出最优解的性质，并刻划其结构特征。找出最优解的性质，并刻划其结构特征。n 递归地定义最优值。递归地定义最优值。n 计算出最优值。计算出最优值。方法一：自底向上的求解方式方法一：自底向上的求解方式动态规划算法动态规划算法方法二：自上而下方法二：自上而下+ +备忘录的求解方式备忘录的求解方式备忘录

3、算法备忘录算法n 根据计算最优值时得到的信息，构造最优解。实际应根据计算最优值时得到的信息，构造最优解。实际应用中，为了描述如何得到这个最优解，通常在自底向上的用中，为了描述如何得到这个最优解，通常在自底向上的求解过程中，把每一个子问题中所作的选择保存在一个表求解过程中，把每一个子问题中所作的选择保存在一个表格中。格中。3.1 3.1 矩阵连乘问题矩阵连乘问题n 给定给定n个矩阵：个矩阵：A1, A2, , An，其中，其中Ai与与Ai+1是可是可乘的。确定一种连乘的顺序，使得矩阵连乘的计算乘的。确定一种连乘的顺序，使得矩阵连乘的计算量为最小。量为最小。n 设设A和和B分别是分别是pq和和qr

4、的两个矩阵，则乘积的两个矩阵，则乘积C=AB为为pr的矩阵，计算量为的矩阵，计算量为p*q*r次数乘。次数乘。n 但是对于多于但是对于多于2个以上的矩阵连乘，连乘的顺序个以上的矩阵连乘，连乘的顺序却非常重要，因为不同的顺序的总计算量将会有很却非常重要，因为不同的顺序的总计算量将会有很大的差别。大的差别。不同计算顺序的差别不同计算顺序的差别求多个矩阵的连乘积时，计算的结合顺序是十分重要的。求多个矩阵的连乘积时，计算的结合顺序是十分重要的。对穷举搜索法的思考对穷举搜索法的思考n 穷举法：列举出所有可能的计算次序，并计算穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中

5、找出出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。一种数乘次数最少的计算次序。 n n个矩阵的连乘积至少有个矩阵的连乘积至少有(4n/n3/2)个不同的计算顺个不同的计算顺序，即序，即计算顺序计算顺序随随n n的增长呈指数增长的增长呈指数增长。因而穷举。因而穷举搜索法对此问题不是有效的算法。搜索法对此问题不是有效的算法。使用动态规划法求解使用动态规划法求解将矩阵连乘积将矩阵连乘积 简记为简记为Ai:jAi:j ，这里，这里ij ij jiiAAA.1考察计算考察计算Ai:jAi:j的最优计算次序。设这个计算次序的最优计算次序。设这个计算次序在矩阵在矩阵A Ak k和和

6、A Ak+1k+1之间将矩阵链断开之间将矩阵链断开，ikjikj，则其，则其相应相应完全加括号方式为完全加括号方式为).)(.(211jkkkiiAAAAAA计算量：计算量：Ai:kAi:k的计算量的计算量加上加上Ak+1:jAk+1:j的计算量的计算量，再加上再加上Ai:kAi:k和和Ak+1:jAk+1:j相乘的计算量相乘的计算量。动态规划法求解步骤动态规划法求解步骤1 1分析最优解的结构分析最优解的结构思考：思考：将矩阵连乘积将矩阵连乘积A Ai iA Ai+1i+1A Aj j记为记为Ai: jAi: j。若若A1: n A1: n 的一个的一个最优解最优解是在矩阵是在矩阵A Ak k

7、和和A Ak+1k+1处断开处断开的，即的，即 A1: n = ( A1: k Ak+1: n )A1: n = ( A1: k Ak+1: n )，则则 A1: k A1: k 和和 Ak+1: n Ak+1: n 也也分别是最优解分别是最优解。 为什么？为什么？ 矩阵连乘计算次序问题的最优解包含着其子问矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为题的最优解。这种性质称为最优子结构性质最优子结构性质。问题。问题的的最优子结构性质最优子结构性质是该问题可用是该问题可用动态规划动态规划算法求解算法求解的的显著特征显著特征。动态规划法求解步骤动态规划法求解步骤2 2建立递归关系

8、建立递归关系 令令mij(1i, jn)为计算为计算Ai, j 的最少乘次数，的最少乘次数，则原问题为求则原问题为求m1n的值。的值。 当当i = j时，时，Ai, j为单一矩阵，为单一矩阵， mij = 0； 当当ij时，利用最优子结构性质有：时，利用最优子结构性质有： 根据此递归式就可以直接用递归程序来实现。根据此递归式就可以直接用递归程序来实现。 ( P54 RecurMatrixChain)mij = min mik + mk+1j + pi1pkpj ikj 其中矩阵其中矩阵A Ai i(1in)(1in)的维数为的维数为p pi i1 1p pi i。mij = min mik +

9、 mk+1j + pi1pkpj ikj动态规划法求解步骤动态规划法求解步骤3 3计算出最优值计算出最优值P54：RecurMatrixChain直接递归的时间复杂性直接递归的时间复杂性RecurMatrxChain的时间复杂性为：的时间复杂性为：解此递归式，得：解此递归式，得： T(n)2T(n)2n n1 1 = (2 = (2n n) )。此算法的时间复杂性随此算法的时间复杂性随n n的指数增长。不可行！的指数增长。不可行！问题出在哪里？问题出在哪里？ n11 + (T(k) + T(nk) + 1) k=1 T(n) 直接递归中有大量重复计算！直接递归中有大量重复计算！如如A1: 4计

10、算中计算中(图中红框标出的都是重复计算图中红框标出的都是重复计算):1: 41: 12: 41: 23: 41: 34: 42: 23: 42: 34: 41:12: 23: 34: 41: 12: 31: 23: 33: 34: 42: 23: 32: 23: 31: 12: 2怎样消除重复的计算？怎样消除重复的计算？n 方法一：自底向上的求解方式方法一：自底向上的求解方式动态规划算法动态规划算法n 方法二：自上而下方法二：自上而下+ +备忘录的求解方式备忘录的求解方式备忘录备忘录算法算法n 注意到在此问题中，注意到在此问题中，不同的有序对不同的有序对 (i, j)就对应不就对应不同的子问题

11、，因此同的子问题，因此不同的子问题个数最多只有不同的子问题个数最多只有 Cn2 + n = ( (n2)个。个。 这样便可以得到多项式时间的算法。这样便可以得到多项式时间的算法。计算最优值方法一：自底向上的方式计算最优值方法一：自底向上的方式例如对于例如对于A A1 1A A2 2A A3 3A A4 4，依据递归式以自底向上的方，依据递归式以自底向上的方式计算出各个子问题，其过程如下：式计算出各个子问题，其过程如下：m11m22m33m44m12m23m34m13m24m14其中其中mii = 0mij = minikj mik+mk+1j+pi1pkpj例如：例如： m13 = min m

12、11+m23+p0p1p3m12+m33+p0p2p3自底向上的算法自底向上的算法输入：输入：n n个连乘矩阵的大小个连乘矩阵的大小p0,p1,p0,p1,pn,pn输出：最少乘法次数记为输出：最少乘法次数记为m1n,m1n,最优解最优解s s算法算法( (思路是自底向上思路是自底向上) )1.1.考虑链长为考虑链长为1 1的情况：的情况：mii=0mii=02.2.考虑链长为考虑链长为r r的情况的情况(r=2:n)(r=2:n)2.1 2.1 对链长为对链长为r r中的每个中的每个mijmij（思考链长为（思考链长为r r中有多中有多少个少个mijmij）2.1.1 2.1.1 计算断点在

13、计算断点在i i处的乘法次数，记为当前的最优处的乘法次数，记为当前的最优值值mij,mij,当前的最优断点为当前的最优断点为i,i,记入记入sij;sij;2.1.2 2.1.2 取取断点值断点值k=i+1k=i+1到到j-1j-1： 计算断点为计算断点为k k处的乘法次数，与已有的最优值处的乘法次数，与已有的最优值mijmij比较，如果当前值更优，则替换比较，如果当前值更优，则替换mijmij和最优断点和最优断点sij;sij;自底向上的矩阵连乘算法自底向上的矩阵连乘算法void MatrixChain(int p, int n, int *m, int *s) for (int i = 1

14、; 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 + pi1*pi*pj; sij = i; for (int k = i + 1; k j; k+) int t = mik + mk+1j + pi1*pk*pj; /对对ikj, 逐个计算逐个计算Ai, j = Ai: k Ak+1: j if (t mij) mij = t; sij = k; /记下较小的记下较小的mij及相应的断点及相应的断点k 自底向上自底向上Mat

15、rixChainMatrixChain算法的运行举例算法的运行举例 设要计算矩阵连乘积设要计算矩阵连乘积A1A2A3A4A5A6，其维数分别，其维数分别为为3535, 3515, 155, 510, 1020, 2025, 即即p0=35, p1=35, p2=15, p3=5, p4=10, p5=20, p6=25。 MatrixChain用矩阵用矩阵mij, sij存放子问题存放子问题Ai: j的最小计算量以及相应的断点。的最小计算量以及相应的断点。123456 1 2 3 4 5 6mij1234561 2 3 4 5 6sijMatrixChain将如下面红色箭头所示的过程逐个计将如

16、下面红色箭头所示的过程逐个计算子问题算子问题Ai: j：执行执行for (int i = 1; i 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;int MemoizedMat

17、rixChain(int n,int *m,int *s) for(int i=1;i=n;i+) for(j=i;i=n;j+) mij=0; return LookupChain(1,n);n 通过通过MatrixChainMatrixChain的计算，我们知道要计算所给的计算，我们知道要计算所给的矩阵连乘积所需的最少数乘次数，但还不知道具的矩阵连乘积所需的最少数乘次数，但还不知道具体应该按什么次序来做矩阵乘法才能达到最少的数体应该按什么次序来做矩阵乘法才能达到最少的数乘次数。乘次数。n sijsij记录矩阵链记录矩阵链Ai:jAi:j的最佳断点。的最佳断点。动态规划法求解步骤动态规划法求

18、解步骤4 4构造最优解构造最优解void Traceback(int i, int j, int * *s) if(i = j) return; Traceback(i, sij, s); Traceback(sij + 1, j, s); cout “ Multiply A “ i “,” sij; cout “ and A “ (sij+1) “,” j endl; 1,1 1,3 2,3s1,6=3 4,62,23,34,56,64,45,5(A1(A2A3)(A4A5)A6) if(i=j) printf(“A%d”,i); else printf( “(“ ); Traceback(

19、i,sij,s); Traceback(sij+1,j,s); printf( “)” ); 动态规划算法的基本方法动态规划算法的基本方法动态规划算法通常可以按以下几个步骤进行：动态规划算法通常可以按以下几个步骤进行： 找出最优解的性质，并刻画其结构特征；找出最优解的性质，并刻画其结构特征； 递归地定义最优值；递归地定义最优值； 以自底向上的方式计算出各子结构的最优值；以自底向上的方式计算出各子结构的最优值； 根据计算最优值时得到的信息，构造最优解。根据计算最优值时得到的信息，构造最优解。 步骤步骤13是动态规划算法的基本步骤。若需要最是动态规划算法的基本步骤。若需要最优解，则必须执行第优解，

20、则必须执行第4步，步，为此还需要在第为此还需要在第3步中记步中记录构造最优解所必需的信息。录构造最优解所必需的信息。3.3 3.3 最长公共子序列最长公共子序列n 若给定序列若给定序列X=x1,x2,X=x1,x2,xm,xm，则另一序列，则另一序列Z=z1,z2,Z=z1,z2,zk,zk，是，是X X的子序列是指存在一个严格递的子序列是指存在一个严格递增下标序列增下标序列i1,i2,i1,i2,ik,ik使得对于所有使得对于所有j=1,2,j=1,2,k,k有：有：z zj j=x=xijij。例如，序列。例如，序列Z=BZ=B，C C，D D，BB是序列是序列X=AX=A，B B，C C

21、，B B，D D，A A，BB的子序列，相应的递增下标序列为的子序列，相应的递增下标序列为22，3 3，5 5，77。n 给定给定2 2个序列个序列X X和和Y Y，当另一序列，当另一序列Z Z既是既是X X的子序列又的子序列又是是Y Y的子序列时，称的子序列时，称Z Z是序列是序列X X和和Y Y的的公共子序列公共子序列。n 给定给定2 2个序列个序列X=x1,x2,X=x1,x2,xm,xm和和Y=y1,y2,Y=y1,y2,yn,yn，找出找出X X和和Y Y的最长公共子序列。的最长公共子序列。最长公共子序列的结构最长公共子序列的结构设序列设序列X=x1,x2,xmX=x1,x2,xm和

22、和Y=y1,y2,ynY=y1,y2,yn的最长的最长公共子序列为公共子序列为Z=z1,z2,zk Z=z1,z2,zk ，则，则(1)(1)若若xm=ynxm=yn，则，则zk=xm=ynzk=xm=yn，且，且Zk-1Zk-1是是Xm-1Xm-1和和Yn-1Yn-1的的最长公共子序列。最长公共子序列。(2)(2)若若xmynxmyn且且zkxmzkxm，则，则Z Z是是Xm-1Xm-1和和Y Y的最长公共的最长公共子序列。子序列。(3)(3)若若xmynxmyn且且zkynzkyn，则，则Z Z是是X X和和Yn-1Yn-1的最长公共的最长公共子序列。子序列。由此可见，由此可见，2 2个序

23、列的最长公共子序列包含了这个序列的最长公共子序列包含了这2 2个序列的个序列的前缀前缀的最长公共子序列。因此，最长公共子序列问题具有的最长公共子序列。因此，最长公共子序列问题具有最优子结最优子结构构性质。性质。 子问题的递归结构子问题的递归结构由最长公共子序列问题的最优子结构性质建立子问题最优值由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。的递归关系。用用cijcij记录序列记录序列XiXi和和YjYj的最长公共子序列的的最长公共子序列的长度。长度。其中，其中， X Xi i=x=x1 1,x,x2 2,x,xi i ；Yj=yYj=y1 1,y,y2 2,y,yj j 。当

24、。当i=0i=0或或j=0j=0时，空序列是时，空序列是X Xi i和和Y Yj j的最长公共子序列。故此时的最长公共子序列。故此时Cij=0Cij=0。其它情况下，由最优子结构性质可建立递归关系。其它情况下，由最优子结构性质可建立递归关系如下：如下：jijiyxjiyxjijijicjicjicjic; 0,; 0,0, 01,1max1 110计算最优值计算最优值由于在所考虑的子问题空间中，总共有由于在所考虑的子问题空间中，总共有(mn)(mn)个不个不同的子问题，因此，用动态规划算法自底向上地计同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。算最优值能提高算法的效率

25、。 实例：实例：n Sample Input：abcfbc abfcabn 算法思路：算法思路：自左而右自上而下建立表格自左而右自上而下建立表格matrixmatrix。(1)(1)如果如果str1istr1istr2jstr2j则将左上角元素值加则将左上角元素值加1 1赋值给赋值给matrixijmatrixij，如果本身是最左上角元素就为，如果本身是最左上角元素就为1 1。(2)(2)如果如果str1istr1i不等于不等于str2jstr2j则该点元素值取则该点元素值取matriximatrixi1j1j和和matrixijmatrixij11中较大的一个。如果中较大的一个。如果i i0

26、 0且且j j0 0（最左上角）（最左上角）则取则取0 0。void 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+) 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; 计算机最优值的算法复杂度分析计算机最优值的算法复杂度分析由于每个数组单元的计算耗时由于每个数组单元的计算耗

27、时O(1)O(1)时间，算法时间，算法LCSLength LCSLength 耗时耗时 O(mn)O(mn)。构造最长公共子序列：构造最长公共子序列：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);构造最优解的算法复杂度分析构造最优解的算法复杂度分析由于每个数组单元的计算耗时由于每个数组单元的计算耗时O(1)O(1)时间，算法时间，算法LCS

28、LCS耗时耗时 O(m+n)O(m+n)。算法空间效率的改进算法空间效率的改进n 在算法在算法lcsLengthlcsLength和和lcslcs中，可进一步将数组中，可进一步将数组b b省去。省去。事实上，数组元素事实上，数组元素cijcij的值仅由的值仅由ci-1j-1ci-1j-1，ci-1jci-1j和和cij-1cij-1这这3 3个数组元素的值所确定。对个数组元素的值所确定。对于给定的数组元素于给定的数组元素cijcij，可以不借助于数组，可以不借助于数组b b而仅而仅借助于借助于c c本身在常数时间内确定本身在常数时间内确定cijcij的值是由的值是由ci-ci-1j-11j-1

29、，ci-1jci-1j和和cij-1cij-1中哪一个值所确定的。中哪一个值所确定的。n 如果只需要计算最长公共子序列的长度，则算法的如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算空间需求可大大减少。事实上，在计算cijcij时，只时，只用到数组用到数组c c的第的第i i行和第行和第i-1i-1行。因此，用行。因此，用2 2行的数组空行的数组空间就可以计算出最长公共子序列的长度。间就可以计算出最长公共子序列的长度。3.10 0-13.10 0-1背包背包n 给定给定n n种物品和一背包。物品种物品和一背包。物品i i的重量是的重量是w wi i，其，其价值为价

30、值为v vi i，背包的容量为，背包的容量为C C。问应如何选择装入背。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大包的物品，使得装入背包中物品的总价值最大? ?n 0-1 0-1背包问题是一个特殊的整数规划问题。背包问题是一个特殊的整数规划问题。nixCxwxviniiiniii1,1 , 0max11最优子结构性质最优子结构性质n若是若是y y1 1,y,y2 2,y,yn n原问题的最优解，则原问题的最优解，则y y2 2,y,yn n将是将是0/10/1背包问背包问题的下述子问题的最优解：题的下述子问题的最优解： nixywcxwxviiniiiniii2,1 , 0ma

31、x122递归关系递归关系n 设所给设所给0-10-1背包问题的子问题背包问题的子问题的最优值为的最优值为m(im(i，j)j)，即，即m(im(i，j)j)是背包容量为是背包容量为j j，可选择，可选择物品为物品为i i，i+1i+1，n n时时0-10-1背包问题的最优值背包问题的最优值。由。由0-10-1背背包问题的最优子结构性质，可以建立计算包问题的最优子结构性质，可以建立计算m(im(i，j)j)的递归的递归式如下：式如下：nkixjxwxvknikkknikkk,1 , 0maxnnniiiiwjwjvjnmwjwjjimvwjimjimjim00),(0), 1(), 1(), 1

32、(max),(未选择物品未选择物品i i的最优解的最优解选择了物品选择了物品i i的最优解的最优解容量不够装物容量不够装物品品i i的情况的情况只剩下最后一个只剩下最后一个物品物品n n的简单情况的简单情况0-10-1背包问题的递归算法背包问题的递归算法n 用二维数组用二维数组mij, 0jc,mij, 0jc,来存储来存储m(i,j)m(i,j)的值。的值。n 求解求解0-10-1背包问题就是在二维数组背包问题就是在二维数组m m中填入相应的值。中填入相应的值。而而m1cm1c中的值就是该背包问题的最优值。中的值就是该背包问题的最优值。n二维数组二维数组m m中最先填入物品中最先填入物品n

33、n的最优值的最优值m(n, j)m(n, j)：若：若0j0jw wn n，mnj=0mnj=0；若；若jwjwn n，mnj=vmnj=vn n。n然后从物品然后从物品n n1 1到物品到物品1 1逐个填入它们的最优值逐个填入它们的最优值m(i, j)m(i, j)：若若0j0jw wi i，mij=mi+1j;mij=mi+1j;若若jwjwi i，mij = mij = maxmi+1j, mi+1jmaxmi+1j, mi+1jw wi i+v+vi i 。n书上给出了此算法的具体实现。书上给出了此算法的具体实现。void Knapsack(Type v,int w,int c,int

34、 n,Typevoid Knapsack(Type v,int w,int c,int n,Type* * * m) m) int jMax=min(wn-1,c); int jMax=min(wn-1,c); for(int j=0;j=jMax;j+) mnj=0; for(int j=0;j=jMax;j+) mnj=0; for(int j=wn;j=c;j+) mnj=vn; for(int j=wn;j1;i-) for(int i =n-1;i1;i-) jMax=min(wi-1,c); jMax=min(wi-1,c); for(int j=0;j=jMax;j+) mij=

35、 mi+1j; for(int j=0;j=jMax;j+) mij= mi+1j; for(int j=wn;j=c;j+) for(int j=wn;j=w1) m1c=max(m2c, m2c-w1+v1); if(c=w1) m1c=max(m2c, m2c-w1+v1); 最优解最优解n 通过通过mijmij里保存的信息，可以很容易地构造里保存的信息，可以很容易地构造出最优解。出最优解。n 先考虑第一个物品：当先考虑第一个物品：当m1c=m2cm1c=m2c时，显时，显然第一个物品是没放入背包的，此时然第一个物品是没放入背包的，此时x x1 1=0=0；否则；否则x x1 1=1=1。n 继续按照此思路，解决剩下的问题。剩下的问继续按照此思路，解决剩下的问题。剩下的问题就为题就为n-1n-1个物品，背包容量为个物品，背包容量为c-xc-x1 1* *w w1 1n 算法在书上，请自学。算法在书上，请自学。0-10-1背包问题算法的复杂性背包问题算法的复杂性n 从算法中可以看出，对每个物品从算法中可以看出，对每个物品i i（第一件除外）（第一件除外）要填入要填入mi