算法设计与分析-动态规划

1、The Design and Analysis of Computer Algorithms 段明秀吉首大学信息科学与工程学院计算机教研室The Design and Analysis of Computer Algorithms 本章学习目标：熟练掌握利用动态规划方法解决问题的基本思想 ；学会如何将问题化为多阶段图的方法；并能对具体问题写出正确的递推公式。 5.1 5.1 动态规划概述动态规划概述5.1.1 5.1.1 什么是动态规划什么是动态规划 在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果

2、。因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策问题。在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态“的含义，称这种解决多阶段决策最优化的过程为动态规划方法。5.1.2 5.1.2 动态规划的基本思想动态规划的基本思想 动态规划的思想在于，假若问题的各个子问题不是独立的，不同的

3、子问题的个数只是多项式量级，假若能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。解决此类问题的过程：首先将问题分为许多阶段，然后再对每一阶段做出决策，而前一阶段的决策恰好又为后一阶段决策的制定提供了有用的信息。在作前一阶段的决策时，根据某些条件，舍弃那些肯定不能得到最优解的局部解，直到做出最后一个阶段的决策并得到问题的解。每一步部经过这样的选取与舍弃后，就可以大大减少计算量。 如果有一个问题，它的过程可以分为若干阶段，而且对于任一阶段i，过程在i阶段以后的行为仅仅依赖于i阶段的状态，而与过程如何达到此种状态（即达到的方式）无关，则称之为一个多阶段

4、的决策过程。解决此类问题的依据是Bellman提出的所谓“最佳（优）性原理（principle of optimality）”：无论过程初始的状态和策略如何，其余的决策必须相对于初始决策所造成的状态构成一个最优的决策序列。最优性原理又被称为最优子结构特性。1. 1. 与分治法的关系与分治法的关系 分治法的基本思想是将问题分解成若干个相互独立的子问题，先求解子问题，然后从这些子问题的解得到原问题的解。在用分治法求解时，由于分解得到的子问题数目太多，有些子问题被重复计算了许多次，以至于最后解决原问题需要耗费指数时间。 动态规划法基本思想也是将待求解问题分解成若干个子问题，与分治法不同的是，适合于用

5、动态规划法求解的问题，经分解得到的子问题往往不是互相独立的，它们可能共享更小的子问题，被称为重叠子问题（overlapping subproblem）。2. 2. 与贪心法的关系与贪心法的关系 动态规划法与贪心法既有相同的地方也有区别。共同点是二者所解决的问题都有很强的步骤性，都要经过多步决策，最终得到最优解。区别在于，贪心法要求针对问题设计最优量度标准，但这在很多情况下并不容易做到，而动态规划法利用最优子结构，自底向上从子问题的最优解逐步构造出整个问题的最优解。所以，动态规划法可以处理不具备贪心准则的问题，这类问题使用贪心法不容易解决。3. 3. 设计动态规划算法设计动态规划算法 通常，设计

6、一个动态规划算法可以按以下4个步骤进行。 （1）找出最优解的性质，并刻画最优解的结构特性； （2）递归定义最优解值； （3）以自底向上方式计算最优解值； （4）根据计算得到的信息构造一个最优解。5.1.3 5.1.3 动态规划的基本要素动态规划的基本要素 一个最优化多步决策问题是否适合采用动态规划法求解，要看它是否具备有两个基本要素：最优子结构特性和子问题重叠性质。 对于一个问题，如果能从较小规模子问题的最优解求得较大规模同类子问题的最优解，最终得到给定问题的最优解，这就是问题最优解的最优子结构特性。 可用动态规划算法求解的问题应该具备的另一个基本要素是子问题的重叠性质。也就是说，在用递归算法

7、自顶向下求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。通常，不同的子问题个数随着问题的大小呈多项式增长。因此，用动态规划算法通常只需要多项式时间，从而获得较高的解题效率。例例 FibonacciFibonacci数列数列无穷数列1，1，2，3，5，8，13，21，34，55，称为Fibonacci数列。它可以递归地定义为：边界条件边界条件递归方程递归方程110)2() 1(11)(nnnnFnFnF第n个Fibonac

8、ci数可递归地计算如下：int fibonacci(int n) if (n = 1) return 1; return fibonacci(n-1)+fibonacci(n-2); 要统计计算fib(n)需要递归调用fibonacci函数的次数，只要增加一个全局变量即可。 Num=0;int fibonacci(int n) Num+; if (n = 1) return 1; return fibonacci(n-1)+fibonacci(n-2); 如果我们调用fib(5)，将产生一棵对于同一值重复计算多次的调用树： fib(5) fib(4) + fib(3) (fib(3) + fi

9、b(2) + (fib(2) + fib(1) (fib(2) + fib(1) + (fib(1) + fib(0) + (fib(1) + fib(0) + fib(1) (fib(1) + fib(0) + fib(1) + (fib(1) + fib(0) + (fib(1) + fib(0) + fib(1) 1.特别是，fib(2)计算了3次。在更大规模的例子中，还有更多fib的值被重复计算，将消耗指数级时间。 从上图可知，同一个值被计算了多次，如fib(3)计算了3次，fib (2)计算了5次，也就是说随着程序的运行，进行了很多冗余的计算，也就是计算那些已经知道答案的值，这就产生

10、了重叠，相互之间共享了一些数据，实际上，它们之间共享了很多数据。这种情况很普遍。解决的方法之一是(称为memoization方法或缓存方法) ：在第一次计算出函数值时就把值记下，然后以后需要时进行查找。这种方法在知道会重复使用某个值时很有用。 用这种方法求fib（6）只要调用函数11次。 Fib（30）=1346269 Fib（30）=59 （缓存方法） 该方法的具体做法是设置一个全局数组AN+1,初始值都为0； 对每个I，其Ai为0表示它的值还没计算出来。 /*备忘录方法求解斐波那契数列, 首先去查是否已经被计算出来 过，如果已经计算出来了（其值大于0），则不递归求解其值 ，直 接返回其值即

11、可，否则（其值为0）递归求解其值 */ #include 其值 #define N 6 int aN+1,num; int fac(int n) num+;if (an0) return an; else if (n 1斐波纳契数列F(n)递归 vs 动态规划递归版本:F(n)1if n=0 or n=1 then2return 13else4return F(n-1) + F(n-2)动态规划:F(n)1A0 = A1 = 12for （i = 2；I 1步骤步骤1：用：用F（n）表示在斐波纳契数列中第）表示在斐波纳契数列中第n个数的值；个数的值；步骤步骤2：状态转移方程：状态转移方程：步骤

12、步骤3：以自底向上的方法来计算最优解：以自底向上的方法来计算最优解步骤步骤4：在数组中分析构造出问题的解；：在数组中分析构造出问题的解；F(n) = 1if n = 0 or 1F(n-1) *nif n 1步骤步骤1：用：用F（n）表示）表示n！的值；！的值；步骤步骤2：状态转移方程：状态转移方程：步骤步骤3：以自底向上的方法来计算最优解：以自底向上的方法来计算最优解算法算法5-3：0/1背包问题的动态规划算法。void DKP(float *p, float *w, int n, float M, float &P, int *x) A-1= (0,0); for (i =0; i

13、n-1; n+) A1i=(X, P)|(X-Wi, P-pi)Ai -1, and XM; Ai =MergerPurge(.Ai -1, A1i); /合并两个集合，并删除其中的应去除的阶跃点 (X1, P1)= An-2中最后的阶跃点; (X2, P2)=(X+Wn-1, P+p n-1) ,其中 (X, P)是An-1中使得X+Wn-1M 最大的阶跃点 P=max(P1, P2)； / P为最优值 if (P2P1) x n-1=1; else x n-1= 0; 往回追溯确定x n-2，x n-3，x 0;算法算法5-3：0/1背包问题的动态规划算法。void DKP(float *

14、p, float *w, int n, float M, float &P, int *x) A-1= (0,0); for (i =0; in-1; n+) A1i=(X, P)|(X-Wi, P-pi)Ai -1, and XM; Ai =MergerPurge(.Ai -1, A1i); /合并两个集合，并删除其中的应去除的阶跃点 (X1, P1)= An-2中最后的阶跃点; (X2, P2)=(X+Wn-1, P+p n-1) ,其中 (X, P)是An-1中使得X+Wn-1M 最大的阶跃点 P=max(P1, P2)； / P为最优值 if (P2P1) x n-1=1; e

15、lse x n-1= 0; 往回追溯确定x n-2，x n-3，x 0;图5-1 带权的有向图5.3 0/1背包问题背包问题1. 问题描述问题描述 现在，对4.4节中的背包问题加上一些限制，Xi仅限于取值0或1，即在约束条件下： , M0，Wi0，Xi = 0或1，1 i n使目标函数： , Xi = 0或1，Pi0取极大值，称之为0/1背包问题。2. 最优子结构最优子结构0/l 背包问题的最优解具有最优子结构特性。1niiiW XM1niiiP X3. 3. 求解求解0/10/1背包问题背包问题 如果用Knap（i，j，M）表示由Wi，Wi1，Wj个物品组成的0/1背包问题，那么，原问题就是

16、Knap（1，n，M）。可以通过对n个物品是否加入背包做出一系列决策进行求解，假定变量Xi 0，1，0in表示对物品i是否加入背包的一个决策。Xi1表示将物品i加入背包，Xi0表示不加入背包。假定对这些Xi做出决策的次序是X X1，X2， Xn-1，Xn 。在对X1做出决策后，存在两种情况：（1）X11，将编号为1的物品加入背包，接着求解子问题Knap（2，n，M-W1）；（2）X10，编号为1的物品不加入背包，接着求解子问题Knap（2，n，M）； 若计fj（M）是Knap（j1，n，M）的最优序列的收益值，即f j（M）是当背包载重为M，可供选择的物品为j1，j2，n（1jn）时的最优解的

17、效益值。那么，可表示f0（M）得到如下关系式： f0（M）max f1（M），f1（M -W1）P1 （5-2） 一般地，由于Xi可能的取值也是0和1，故有递推关系式：f j（x） max f j1（x），f j1（xW j1）P j1 显然，推到是否添加第n个物品是，规定：当x0时，有f n（x） 0；当x0，f n（x）（此定义有一定的人为性）。由这些初始条件，往回递推下去，就可以得到f 0（M），即Knap（l，n，M）的最优解的值，此即前一节中提到的向前处理法. 现在，我们改变一下计算方向。假定对这些Xi做出决策的次序是X Xn，Xn-1，X1。在对Xn做出决策后，存在两种情况：（1）

18、Xn1，将编号为n的物品加入背包，接着求解子问题Knap（1，n-1，M-Wn）；（2）Xn0，编号为n的物品不加入背包，接着求解子问题Knap（1，n-1，M）；假设fi（M）是Knap（i，n，M）的最优解的值，即fi（M）是当背包载重为M，可供选择的物品为n，i1，i，（1in）时的最优解值，那么，fn（M）可表示为： fn（M）max fn-1（M），f n-1（M -Wn） Pn （5-4）依次递推下去，直到f1（M），即有： f1（M） maxf0（M），f0（MW1）P1 在初始时设定，对x0时，有f0（x） 0；对x0，f0（x）。于是，可以由f0开始，推算出fn（M），即Kn

19、ap（l，n，M）的最优解的值， 此即动态规划的向后处理法。 一般地，有： fi（x） maxfi1（x），fi1（xWi）Pi 【例例5-2】考虑前面提到的背包问题， n3，（W1，W2，W3）（3，4，5），（P1，P2，P3）（5，6，10），M7。解：01001121122,0( )0,0,0( )max( ),()max0,50,03max0,055,3,0max0,60,03( )max ( ),()max5,65,34max5,066,47max5,5611,xfxxxf xfxfxWPxxxxfxf xf xWPxx 322337()max(),()max11,01011xf

20、MfMfMWP 因此，背包问题Knap（l，3，7）的最优解值为l1。仔细检查fi（x）的取值，往前追溯，就可以知道此最优序列是（l，l，0）。 4. 算法描述算法描述算法算法5-2：0/1背包的递归算法。templatec1ass Knapsack public: Knapsack(int mSize, float cap, float *wei, T *prof) T RKnapQ; private: T (int j，foat X); Float m,*w; T *p; int n;templateT Knapsack:(int j，f1oat X) if (t0) return (X0

21、) ? INFTY：0) if (Xb) return a else retum b; templateT Knapsack: RKnap（） if (n0) return (n-1, m); else retum NoAns; /NoAns 为无收益量设T（n）为当物品数目为n时，分析此递归算法可得到如下递推关系式： T（0）= C1 n=1 T（1）= C1 n=1 T（n） 2 T（n-1）+ C2 n1式中，C1和C2是常数。解这一递归方程，得T（n）= O（2 n）。 5. 改进的算法改进的算法图5-3 背包问题的图解法给定n个矩阵 ， 其中 与 是可乘的， 。考察这n个矩阵的连乘积

22、 由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积,.,21nAAAiA1iA1,.,2 , 1ninAAA.21（1）单个矩阵是完全加括号的；（2）矩阵连乘积 是完全加括号的，则 可 表示为2个完全加括号的矩阵连乘积 和 的乘积并加括号，即 AABC)(BCADCBA , , ,1050A4010B3040C530D)(DBCA)(DCAB)(DBCA)(CDBA)(CDAB16000, 10500, 3600

23、0, 87500, 34500完全加括号的矩阵连乘积可递归地定义为：设有四个矩阵 ，它们的维数分别是：总共有五种完全加括号的方式 每一种完全加括号的方式对应于一个矩每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积阵连乘积的计算次序，这决定着作乘积所需要的计算量。若所需要的计算量。若A A是一个是一个p pq q矩阵，矩阵，B B是一个是一个q qr r矩阵，则计算其乘积矩阵，则计算其乘积C=ABC=AB的的标准算法中，需要进行标准算法中，需要进行pqrpqr次数乘。次数乘。两个矩阵乘积for(i=1； i =p;+ i) for(j=1;j=r;+j) cij=0; for

24、(k=1;k=q;+k) cij+=aik*bkj; 矩阵矩阵A 和和B可乘的条件是矩阵可乘的条件是矩阵A的列数等于矩的列数等于矩阵阵B的行数。的行数。 为了说明在计算矩阵连乘积时，加括号方式对为了说明在计算矩阵连乘积时，加括号方式对整个计算量的影响，先考察整个计算量的影响，先考察3 3个矩阵个矩阵AA1 1,A,A2 2,A,A3 3 连乘的情况。设这三个矩阵的维数分别为连乘的情况。设这三个矩阵的维数分别为1010100100，1001005 5，5 55050。加括号的方式只有。加括号的方式只有两种：（两种：（A A1 1A A2 2）A A3 3），（），（A A1 1（A A2 2A

25、A3 3），第一），第一种方式需要的数乘次数为种方式需要的数乘次数为10101001005 510105 5505075007500，第二种方式需要的数乘次，第二种方式需要的数乘次数为数为1001005 55050101010010050507500075000。第二。第二种加括号方式的计算量时第一种方式计算量的种加括号方式的计算量时第一种方式计算量的1010倍。由此可见，在计算矩阵连乘积时，加括倍。由此可见，在计算矩阵连乘积时，加括号方式，即计算次序对计算量有很大的影响。号方式，即计算次序对计算量有很大的影响。 于是，自然提出矩阵连乘积的最优计算于是，自然提出矩阵连乘积的最优计算次序问题，即

26、对于给定的相继次序问题，即对于给定的相继n n个矩阵个矩阵AA1 1,A,A2 2,A,An n （其中矩阵（其中矩阵A Ai i的维数为的维数为p pi-i-1 1p pi i，i i1,2,n1,2,n），如何确定计算矩），如何确定计算矩阵连乘积阵连乘积A A1 1A A2 2AAn n的计算次序（完全加括的计算次序（完全加括号方式），使得依此次序计算矩阵连乘号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少。积需要的数乘次数最少。 穷举搜索法的计算量太大，它不是一个穷举搜索法的计算量太大，它不是一个有效的算法，有效的算法， 穷举法：列举出所有可能的计算次序，穷举法：列举出所有可能的计

27、算次序，并计算出每一种计算次序相应需要的数并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的乘次数，从中找出一种数乘次数最少的计算次序计算次序。算法复杂度分析：算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1An)可以得到关于P(n)的递推式如下：)/4()(11)()(1)(2/311nnPnnknPkPnPnnku动态规划动态规划将矩阵连乘积 简记为Ai:j ，这里ij jiiAAA.1考察计算Ai:j的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，ikj

28、，则其相应完全加括号方式为).)(.(211jkkkiiAAAAAA计算量：Ai:k的计算量加上Ak+1:j的计算量，再加上Ai:k和Ak+1:j相乘的计算量特征：计算Ai:j的最优次序所包含的计算矩阵子链 Ai:k和Ak+1:j的次序也是最优的。矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。设计算Ai:j，1ijn，所需要的最少数乘次数mi,j，则原问题的最优值为m1,n 当i=j时，Ai:j=Ai，因此，mi,i=0，i=1,2,n当ij时，可以递归地定义mi,j为：jkipppjk

29、mkimjim1, 1,这里 的维数为 iAiipp1jipppjkmkimjijimjki, 1,min0,1jki 的位置只有 种可能kij 对于1ijn不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有当Ij时，不同子问题的个数为，I=j时，不同子问题的个数为n。由此可见，在递归计算时，许多子问题被重复计算多次许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到

30、多项式时间的算法)(22nnn1 2 51 3 51 4 522350 2500 35 15 20 1300025 m in23452625 1000 35 5 20 712524554375 0 35 10 20 11375mmpp pmmmpppmmpp p 其中Ai矩阵的维数为pi-1，pi，如A1矩阵的行为p0=30，列数为p1=35 填表规律： 1.先填对角线数据，因为mII=0; 2.由于求mIj，其条件要求Ij;因此只会填上三角矩阵。 3. 可知，其填充方式如下图a所示：jipppjkmkimjijimjki, 1,min0,1jki 由计算次序可知， R=1时，是计算对角线数据

31、，即for (int i = 1; i = n; i+) mii = 0; 其他计算次序即图中向下斜箭头所示共循环n-1次（共n-1=5个向下斜箭头）。 即for (r=2；r=n;r+) 对每个向下斜箭头其元素mIj, I控制行，由图可知， I总是从第一行开始，到n-r+1结束。 如当r=2时，是计算m12,m23,m34,m45,m56这些元素的值。这里I=1，i=n-r+1;I+ J控制列，void MatrixChain(int *p，int n，int *m，int *s) for (int i = 1; i = n; i+) mii = 0; for (int r = 2; r =

32、 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; 算法复杂度分析：算法复杂度分析：算法matrixChain的主要计算量取决于算法中对r，i和k的3重循环。循环体内的计算量为O(1)，而3重循环的总次数为O(n3)。因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。设q =

33、 5和p =（10 , 5 , 1 , 10 , 2 , 10）求解MPCc(2,5)=minc(2,2)+c(3,5)+50, c(2,3)+c(4,5)+500, c(2,4)+c(5,5)+100c(1,5)=min c(1,1)+c(2,5)+500， c(1,2)+c(3,5)+100, c(1,3)+c(4,5)+1000, c(1,4)+c(5,5)+200c(1,5)=190,kay(1,5)=2c(3,5)=minc(3,3)+c(4,5)+100, c(3,4)+c(5,5)+20 =min300,40c(3,5)=40,kay(3,5)=4c(2,4)=minc(2,2)

34、+c(3,4)+10, c(2,3)+c(4,4)+100 =min30,150c(2,4)=30,kay(2,4)=2c(2,5)=90,kay(2,5)=2c(1,3)=150,kay(1,3)=2c(1,4)=90,kay(1,4)=2M(1,5)=M(1,2)M(3,5)M(3,5)=M(3,4)M(5,5) 4.构造最优解构造最优解算法算法matrixChain只是计算出了最优值，但只是计算出了最优值，但未给出最优解，事实上未给出最优解，事实上matrixChain已记录了已记录了构造最优解所需要的全部信息。构造最优解所需要的全部信息。 sij中的数表明，计算矩阵链中的数表明，计算矩

35、阵链Ai:j的最佳的最佳方式应在矩阵方式应在矩阵A(k)和矩阵和矩阵A(k+1)之间断开，因之间断开，因此可递推得此可递推得A1:n的最优完全加括号方式，即的最优完全加括号方式，即构造出问题的一个最优解。构造出问题的一个最优解。 void traceBack(int i, int j, int *s) if(i = j) return; traceBack(i, sij, s); traceBack(sij+1, j, s); printf(链应该断在k = %d 的位置上/n, sij);矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质最优子结构性质。在分析问题

36、的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。 利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低） 递归算法：RecurMatrixchain(int i,int j) int t,u,k; if (i=j) return 0; else u= RecurMatrixchain (i,i)+ Re

37、curMatrixchain(i+1,j)+pi-1*pi*pj; sij=i; for (k=i+1;kj;k+) t= RecurMatrixchain (i,k)+ RecurMatrixchain(k+1,j) +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(

38、k+1，j) + pi-1*pk*pj; if (t =- yj:xmy1y2ynx1x2xii012nm120firstsecond步骤步骤3附加信息yj:DACFABxiji012nm120矩阵 bi, j:它告诉我们要获得最优结果应该如何选择如果 xi = yjbi, j = 1如果 ci - 1, j ci, j-1bi, j = 2否则bi, j = 333CDci,j-1ci-1,j0if 0 or 0, , 1,11if ,0 and ,max( 1, , ,1)if ,0 and .ijijijc i jc iji jxyc ij c i ji jxy=-+=- 例子X = (

39、B, D, C, A, B, A)Y = (A, B, C, B, D, A,B)0126345yjBDACAB51203467DABxiCBAB00000000000000000 11 1 1111 2211 2222 1122 331 222331232 3 4 1223 44如果 xi = yj bi, j = “ ”如果 ci - 1, jci, j-1bi, j = “ ”否则bi, j = “ ”由于在所考虑的子问题空间中，总共有(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。 void LCSLength(int m，int n，char *x，

40、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; 构造最长公共子序列构造最长公共子序列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); coutb) re

41、turn a; else return b; Lcs(char x,char y,int I,int j) int k; if (I=0|j=0) return 0; if (xI=yj) k=lcs(x,y,I-1,j-1)+1; else k=max(lcs(x,y,I-1,j), lcs(x,y,I,j-1); Return k; main() char XN+2= abcbdab,YM+2= bdcaba;/因为比较的是x1.N和Y1.M其相应存储下标为1.N,1.M，因此0单元要浪费，另外要存储字符串结束符0，因此要多开辟一个单元，因此总存储空间要浪费2个 int i,j; int

42、u; u=Recurlcs(X,Y,N,M); printf(%dn,u);备忘录方法 Lcs(char x,char y,int I,int j) if (I=0|j=0) return 0; If(cIj=0) if (xI=yj) cIj=lcs(x,y,I-1,j-1)+1; else cIj= max(lcs(x,y,I-1,j), lcs(x,y,I,j-1); Return cIj; 在算法lcsLength和lcs中，可进一步将数组b省去。事实上，数组元素cij的值仅由ci-1j-1，ci-1j和cij-1这3个数组元素的值所确定。对于给定的数组元素cij，可以不借助于数组b而

43、仅借助于c本身在时间内确定cij的值是由ci-1j-1，ci-1j和cij-1中哪一个值所确定的。如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算cij时，只用到数组c的第i行和第i-1行。因此，用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n)。最大子段和问题 一.问题描述 给定长度为n的整数序列，a1.n, 求1,n某个子区间i , j使得ai+aj和最大.或者求出最大的这个和.例如(-2,11,-4,13,-5,2)的最大子段和为20,所求子区间为2,4. 解题方法穷举穷举 1.穷举思路,对于起点 i，我们遍

44、历所有长度为1,2,n-i+1的子区间和，以求得和最大的一个.这样也遍历了所有的起点的不同长度的子区间，同时，对于相同起点的不同长度的子区间，可以利用前面的计算结果来计算后面的. max(int a,int n) int max1=0,i,j,b; for (i=0;in;i+) b=0; for (j=i;jmax1) max1=b; return max1; main() int a=-2,11,-4,13,-5,-2; printf(%d,max(a,6); 2.分治法分治法求子区间及最大和，从结构上是非常适合分治法的，因为所有子区间start, end只可能有以下三种可能性: 在1,

45、n/2这个区域内在n/2+1, n这个区域内起点位于1,n/2,终点位于n/2+1,n内 以上三种情形的最大者，即为所求. 前两种情形符合子问题递归特性，所以递归可以求出. 对于第三种情形，则需要单独处理. 第三种情形必然包括了n/2和n/2+1两个位置，这样就可以利用第二种穷举的思路求出: 以n/2为终点，往左移动扩张，求出和最大的一个left_max以n/2+1为起点，往右移动扩张，求出和最大的一个right_maxleft_max+right_max是第三种情况可能的最大值分治法分治法实现要点实现要点 函数参数:要求解的数组,a=-2,11,-4,13,-5,2,要求解的区域,左边界l和

46、右边界r;函数要将求得的最大子段和的值返回.因此函数头为int zuidaziduanhefenzhi(int a,int l,int r)1.递归出口: 只有一个元素时结束: 如果该元素大于0,则结果就是该元素; 如果该元素是负数,则结果用0表示 即if (l=r) he=al0?al:0; 用递归的方法求解if (l=l;i-) suml+=ai; if (sumlleftmax) leftmax=suml; 往往右右求出最大子段和求出最大子段和;用用rightmax存储从m开始往右的最大子段和。sumr=0;for (i=m+1;irightmax) rightmax=sumr; /求出

47、三者的最大数。 he=sanzhemax(lefthe,righthe,leftmax+rightmax);#include int sanzhemax(int a,int b,int c)int m;if (aa) return c;else return a;int zuidaziduanhefenzhi(int a,int l,int r)int i,m,lefthe,righthe,leftmax=0,rightmax=0,suml=0,sumr=0,he=0;if (l=r) he=al0?al:0; elsem=(l+r)/2;lefthe=zuidaziduanhefenzhi(

48、a,l,m);/求出左半部分的最大子段和,用lefthe存储righthe=zuidaziduanhefenzhi(a,m+1,r);/求出右半部分的最大子段和,用righthe存储/求中间部分的最大子段和,因为是连续区间,一定包含划分点m,因此以它为界,往左求出最大子段和;往右求出最大子段和;suml=0;for (i=m;i=l;i-) suml+=ai; if (sumlleftmax) leftmax=suml;sumr=0;for (i=m+1;irightmax) rightmax=sumr;he=sanzhemax(lefthe,righthe,leftmax+rightmax)

49、;return he;void main() int he,a=-2,18,-4,13,-5,2,2; he=zuidaziduanhefenzhi(a,0,6); printf(%d,he); 3.动态规划法 令bj表示以位置 j 为终点的所有子区间中和最大的一个 子问题:如j为终点的最大子区间包含了位置j-1,则以j-1为终点的最大子区间必然包括在其中 如果bj-1 0, 那么显然bj = bj-1 + aj，用之前最大的一个加上aj即可，因为aj必须包含 如果bj-1=0 或者 si = ai; si-1 0), your task is to find m pairs of i and

50、 j which make sum(i1, j1) + sum(i2, j2) + sum(i3, j3) + . + sum(im, jm) maximal (ix iy jx or ix jy jx is not allowed). But Im lazy, I dont want to write a special-judge module, so you dont have to output m pairs of i and j, just output the maximal summation of sum(ix, jx)(1 x m) instead. _ Input Eac

51、h test case will begin with two integers m and n, followed by n integers S1, S2, S3 . Sn. Process to the end of file. Output Output the maximal summation described above in one line. Sample Input 1 3 1 2 3 2 6 -1 4 -2 3 -2 3 Sample Output 6 8 #include #define N 6 #define M 1 int mziduanhe(int a) int

52、 i,j,t,current,max,bM+1N+1; /初始化 for (i=0;i=M;i+) for (j=0;j=N;j+) bij=0; for (i=1;i=M;i+) for (j=i;j=N;j+) bij= bi-1i-1; for (t=i;t bij) bij=current;bij+=aj;if (bij-1+ajbij) bij=bij-1+aj; max=bii; for (j=i+1;jmax) max=bij; return max; void main() int a=0,-2,11,-4,13,-5,-2; printf(%d,mziduanhe(a); d

53、pij表示前j个元素分成i段的最优解，同时这个最优解是由aj元素结束的。 转移方程是dpij=maxfij-1+aj，fi-1k+aj,(i-1=kj) (i=j=n-m+i) 其中j的上下界的确定比较麻烦。现在分别解释上界和下界： 上界：dpij中，如果j=i-1，意思就是在前面i-1个元素中分成i段，这个是不可能实现的。 下界：如果m=n=4，这时dp24求出来了，意思是前面的四个元素分成了两段，当是还有两段要分， 所以求出这个是没有意义的。当然求出来也不会影响结果，只是这样时间复杂度就提高了。 这是其中一个特例的状态转移表 m=4，n=6 ，-1 4 -2 3 -2 3 没有填的说明不用

54、算。 很显然dpii=dpi-1i-1+ai, 所以对角线上面有： 现在演示一下转移过程。如何求下图的框中的元素的值 由下面涂色的元素的最大值加上a3=-2求的如下图 最大的是4，所以4+（-2）=2；框中填2; 假如框中的元素是dpij,画圈的元素表示的是，左边那个是dpij-1,上面的几个是dpi-1k(i-1=kj) ，这个就是上面的转移方程的表格表示法。最大子矩阵和问题 给定一个n*n(0n=100)的矩阵，请找到此矩阵的一个子矩阵，并且此子矩阵的各个元素的和最大，输出这个最大的值。 Example： 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 其中左

55、上角的子矩阵： 9 2 -4 1 -1 8 此子矩阵的值为9+2+(-4)+1+(-1)+8=15。 #include #define N 4 #define M 4 int yiwei(int a,int n) int i,b=0,max=0; for (i=0;i0) b+=ai; else b=ai; if (bmax) max=b; return max; void main() int aMN=0,-1,-7,0,19,2,-6,2,-4,1,-4,1,-1,18,0,-2; printf(%d,zuidazijuzhen(a); 假设最大子矩阵的结果为从第r行到k行、从第i列到j列

56、的子矩阵，如下所示(ari表示ari,假设数组下标从1开始)：| a11 a1i a1j a1n | | a21 a2i a2j a2n | | . . . . . . . | | . . . . . . . | | ar1 ari arj arn | | . . . . . . . | | . . . . . . . | | ak1 aki akj akn | | . . . . . . . | | an1 ani anj ann | 那么我们将从第r行到第k行的每一行中相同列的加起来，可以得到一个一维数组如下： (ar1+ak1, ar2+ak2, ,arn+akn) 由此我们可以看出最后

57、所求的就是此一维数组的最大子断和问题，到此我们已经将问题转化为上面的已经解决了的问题了。给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?0-1背包问题是一个特殊的整数规划问题。niiixv1maxnixCxwiniii1,1 , 01 在选择装入背包的物品时，对物品i只有两种选择， 即装入或不装入背包。不能将物品i装入多次，也 不能只装入部分的物品i。考虑有三种物品考虑有三种物品,它们的它们的重量为重量为(w1,w2,w3)=(2,3,4),价值为价值为(v1,v2,v3)=(1,2,5),当背包容量为当背包容

58、量为c=6时，如何装背包总价值最大？时，如何装背包总价值最大？x1,x2,x3=1,0,1v1*x1+v2*x2+v3*x3=6x1,x2,x3=0,0,01,0,00,1,00,0,11,1,01,0,1定理：定理：0-1背包问题具有最优子结构性质背包问题具有最优子结构性质 设(y1,y2,.,yn)是给定0-1背包问题的一个最优解，则必有结论，(y2,y3,.,yn)是如下子问题的一个最优解：证明： 因为，若因为，若(z2, zn )是下述子问题的一个最优解，而是下述子问题的一个最优解，而（y2, yn）不是它的最优解）不是它的最优解这说明这说明(y1,z2,zn)是所给问题的一个更优解，

59、是所给问题的一个更优解，从而从而(y1,y2,yn)不是原问题的最优解，矛盾不是原问题的最优解，矛盾x1vixi则则 niiiniiiniiiczwywyvzv21122，且且czwywyvzvyvniiiniiiniii 2111211因此因此设背包问题的子问题的最优值为设背包问题的子问题的最优值为m( i, j ),即即m( i, j)是背包容是背包容量为量为j，可选择物品为，可选择物品为i，i1，, n时的最优值时的最优值,即最大总价即最大总价值。值。当选择第当选择第i个物品时，个物品时， 。 如果不选择第如果不选择第i个物品，则个物品，则 。由问题的最优子结构性质，我们可以建立计算由问

60、题的最优子结构性质，我们可以建立计算m( i, j)的递归式如下：的递归式如下： iiiiwjjimwjvwjimjimjim0), 1(), 1(), 1(max),( nnnwjwjvjnm00),(m(i,j)=m(i+1,j-wi)+vim(i,j)=m(i+1,j)0-1背包问题背包问题例例:四个物品，背包容积为四个物品，背包容积为5，w4=2,1,3,2，v4=12,10,20,15，求最大价值，求最大价值m1c及选取的物品编号及选取的物品编号43214321050000010 1515 15 151515 2020 3535302537ijnnnwjwjvjnm00),( iiiiwjjimwj