《计算机算法设计与分析》PPT第三章 动态规划

1第3章动态规划2

学习要点:理解动态规划算法概念。掌握动态规划算法基本要素(1)最优子结构性质(2)重叠子问题性质掌握设计动态规划算法的步骤。(1)找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。3通过应用范例学习动态规划算法设计策略。（1）矩阵连乘问题（2）最长公共子序列（3）最大子段和（4）凸多边形最优三角剖分（5）多边形游戏（6）图像压缩（7）电路布线（8）流水作业调度（9）背包问题（10）最优二叉搜索树4历史及研究问题动态规划（dynamicprogramming）是运筹学的一个分支，20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(Multistepdecisionprocess)的优化问题时，提出了著名的最优性原理，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。多阶段决策问题：求解的问题可以划分为一系列相互联系的阶段，在每个阶段都需要做出决策，且一个阶段决策的选择会影响下一个阶段的决策，从而影响整个过程的活动路线，求解的目标是选择各个阶段的决策使整个过程达到最优。5动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），可以人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。动态规划是考察问题的一种途径，或是求解某类问题的一种方法。动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比其它方法求解更为方便。6基本概念①状态：表示每个阶段开始时，问题或系统所处的客观状况。状态既是该阶段的某个起点，又是前一个阶段的某个终点。通常一个阶段有若干个状态。状态无后效性：如果某个阶段状态给定后，则该阶段以后过程的发展不受该阶段以前各阶段状态的影响，也就是说状态具有马尔科夫性。适于动态规划法求解的问题具有状态的无后效性②策略：各个阶段决策确定后，就组成了一个决策序列，该序列称之为一个策略。由某个阶段开始到终止阶段的过程称为子过程，其对应的某个策略称为子策略。7最优性原理Bellman最优性原理求解问题的一个最优策略序列的子策略序列总是最优的，则称该问题满足最优性原理。注：对具有最优性原理性质的问题而言，如果有一决策序列包含有非最优的决策子序列，则该决策序列一定不是最优的。8动态规划的思想实质是分治思想和解决冗余动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=算法总体思想9但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。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)算法总体思想10如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。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)算法总体思想11动态规划基本步骤找出最优解的性质，并刻划其结构特征。递归地划分子问题，递归地定义最优值，给出最优解的递归式。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。注：步骤①~③是动态规划算法的基本步骤。如果只需要求出最优值的情形，步骤④可以省略；若需要求出问题的一个最优解，则必须执行步骤④，步骤③中记录的信息是构造最优解的基础；12给定n个矩阵，其中与是可乘的，。考察这n个矩阵的连乘积由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积3.2矩阵连乘问题13完全加括号的矩阵连乘积

完全加括号的矩阵连乘积的递归定义：（1）单个矩阵是完全加括号的；（2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即1415矩阵连乘问题问题描述给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，矩阵Ai的维数为pi-1×pi，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。注意①设Ap×q,Aq×r两矩阵相乘，普通乘法次数为p×q×r；②加括号对乘法次数的影响1617穷举法列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下：因此，穷举法不是一个有效算法。呈指数增长18计算量小的优先计算n个矩阵的连乘积共有n-1次乘法计算。首先在n-1次乘法计算中选择乘法计算量最小的两个矩阵优先计算，然后再在剩下的n-2次乘法计算中选择计算量最小的两个矩阵进行计算，依此往下。该解决策略在某些情况下可得到最优解，但在很多情况下得不到最优解。如上例的第(5)种完全加括号方式即采用该策略，但得到的显然不是最优解。19矩阵维数大的优先计算在n个矩阵的n+1个维数序列p0,p1,p2,…,pn中选择维数的最大值（设为pi），并把相邻两个含有维数pi的矩阵优先进行计算，然后在剩下的n个维数序列中再次选择维数的最大值，进行相应矩阵的乘法运算，依此往下。该策略与上一种策略相似，在某些情况下可得到最优解，但在有些情况下得不到最优解。如上例的第(3)种完全加括号方式就是采用该策略，显然它得到的是最优解。当４个矩阵的维数改为50×10,10×40,40×30和30×5时，可验证采用该策略得到的不是最优解。以上两种策略实质都是基于某种贪心选择的贪心算法，这种算法不一定能得到问题的全局最优解。在下一章我们将详细讨论此种策略。20分治法将矩阵连乘积AiAi+1…Aj简记为A[i:j]。设n个矩阵的连乘积A1A2…An的计算次序在矩阵Ak和Ak+1之间将矩阵链断开，1≤k<n，则其相应的完全加括号方式为(A1...Ak)(Ak+1…An)。完全加括号是一个递归定义，可递归地计算A[1：k]和A[k+1:n]，然后将计算结果相乘得到A[1：n]。可设计如下递归算法recurmatrixChain：2122该递归算法的的计算时间T(n)可递归定义如下：当n>1时，该算法的计算时间T(n)有指数下界。分治法是该问题的一个可行方法，但不是一个有效算法。23为何分治法的效率如此低下？recurmatrixChain(1,4)计算A[1：4]的递归树。从图中可看出，许多子问题被重复计算。这是分治法效率低下的根本原因。24该问题可用分治思想解决，并存在大量冗余，可用动态规划求解。动态规划25矩阵连乘问题将矩阵连乘积简记为A[i:j]，i≤j。考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，i≤k<j，则其相应完全加括号方式为计算量为A[i:k]的计算量加上A[k+1:j]的计算量，再加上A[i:k]和A[k+1:j]相乘的计算量261、分析最优解的结构特征计算A[i:j]的最优次序所包含的计算矩阵子链A[i:k]和A[k+1:j]的次序也是最优的。（反证可得）矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。2728假设计算A[i:j](1≤i≤j≤n)所需要的最少数乘次数为m[i,j]，则原问题的最优值为m[1,n]i=j时，A[i:j]=Ai，m[i,i]=0，i=1,2,…,ni<j时，的维数为2、建立递归关系29递归地定义m[i,j]k的位置只有j-i种可能取得的k为A[i:j]最优次序中的断开位置，并记录到表s[i][j]中，即s[i][j]←k。注：m[i][j]实际是子问题最优解的解值，保存下来避免重复计算。30对于1≤i≤j≤n不同的有序对(i，j)对应于不同的子问题。不同子问题的个数最多只有由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。3、计算最优值31用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。32svoidMatrixChain(int*p，intn，int**m，int**s)//n是连乘矩阵数目，A1A2…An；p是矩阵维数，Ai的维数为pi-1×pi(1≤i≤n)；//m是n个矩阵连乘的数乘次数最小值；s存储矩阵连乘的最优计算次序{

for(inti=1;i<=n;i++)m[i][i]=0;//对角线置0,计算Ai...Ai的乘法次数,链长为1for(intr=2;r<=n;r++)//分别计算r个矩阵连乘的最小数乘次数for(inti=1;i<=n-r+1;i++){intj=i+r-1;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//Ai...Aj在矩阵i处断开时的数乘次数s[i][j]=i;//记录取得Ai...Aj当前数乘次数的断开位置for(intk=i+1;k<j;k++){//计算Ai...Aj的最小数乘次数intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}}}3334A1A2A3A4A5A63035351515551010202025算法复杂度分析：算法MatrixChain的主要计算量取决于算法中对r，i和k的3重循环。循环体内的计算量为O(1)，而3重循环的总次数为O(n3)。因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。设要计算矩阵连乘积中各矩阵的维数分别为：354、用动态规划法求最优解MatrixChain已记录了构造最优解所需要的全部信息。S[i][j]表明计算矩阵A[i,j]的最佳方式应在矩阵Ak和Ak+1之间断开，即最优的加括号方式应为(A[i:k])(A[k+1:j])。从s[1][n]记录的信息可知A[1:n]的最优加括号方式为(A[i:s[1][n]])(A[s[1][n]+1:n])。A[i:s[1][n]]的最优加括号方式为(A[i:s[1][s[1][n]]])(A[s[1][s[1][n]]+1:s[1][s[1][n]]]])A[s[1][n]+1:n]的最优加括号方式在s[s[1][n]+1][n]处断开。照此递推，最终可确定A[1:n]的最优完全加括号方式，即构造出问题的一个最优解。36算法traceback：按照MatrixChain计算出的断点s指示加括号方式输出计算A[i:j]的最优计算次序。Voidtraceback(inti,intj,int**s)//按算法MatrixChain计算出的断点矩阵s指示的加括号方式输出计算A[i:j]的最优计算次序{if(i==j)return;traceback(s,i,s[i][j]);traceback(s,s[i][j]+1,j);cout<<“MultiplyA”<<i<<“,”<<s[i][j];cout<<“andA”<<(s[i][j]+1)<<“,”<<j<<endl;}37一、最优子结构矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）3.2动态规划算法的基本要素38二、重叠子问题递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。39三、备忘录方法intLookupChain(inti，intj){if(m[i][j]>0)returnm[i][j];if(i==j)return0;intu=LookupChain(i，i)+LookupChain(i+1，j)+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;k<j;k++){intt=LookupChain(i，k)+LookupChain(k+1，j)+p[i-1]*p[k]*p[j];if(t<u){u=t;s[i][j]=k;}}

m[i][j]=u;returnu;}备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。40动态规划的设计技巧：阶段的划分、状态的表示和存储表的设计在动态规划的设计过程中，阶段的划分和状态的表示是其中最重要的两步，这两步会直接影响该问题的计算复杂性和存储表设计，有时候阶段划分或状态表示的不合理还会使得动态规划法不适用。问题的阶段划分和状态表示，需要具体问题具体分析，没有一个清晰明朗的方法。在实际应用中，许多问题的阶段划分并不明显，这时如果刻意地划分阶段法反而麻烦。一般来说，只要该问题可以划分成规模更小的子问题，并且原问题的最优解中包含了子问题的最优解（即满足最优性原理），则可以考虑用动态规划解决。41如何判断问题满足最优性原理？思路：利用反证法，通过假设每一个子问题的解都不是最优解，然后导出矛盾，即可做到这一点。42例1：设G是一个有向加权图，则G从顶点i到顶点j之间的最短路径问题满足最优性原理。证明：（反证法）设i~ip~iq~j是一条最短路径，但其中子路径ip~iq~j不是最优的。假设最优的子路径为ip~iq’~j，则我们可以重新构造一条路径：i~ip~iq’~j，显然该路径长度小于i~ip~iq~j，与i~ip~iq~j是顶点i到顶点j的最短路径相矛盾。所以，原问题满足最优性原理。43例2：有向图的最长简单路径问题不满足最优性原理。证明：如右图所示，q→r→t是q到t的最长简单路径，而q→r的最长简单路径是q→s→t→r，r→t的最长简单路径是r→q→s→t，但q→r和r→t的最长简单路径合起来并不是q到t的最长简单路径。所以，原问题并不满足最优性原理。注：因为q→r和r→t的子问题都共享路径q→s→t，组合成原问题解时，有重复的路径对原问题是不允许的。44454647484950515253实例二花束摆放问题1、问题描述现有F束不同品种的花束，同时有至少同样数量的花瓶被按顺序摆成一行，其位置固定于架子上，并从1至V按从左到右顺序编号，V是花瓶的数目(F≤V)。花束可以移动，并且每束花用1至F的整数唯一标识。标识花束的整数决定了花束在花瓶中排列的顺序，如果i<j，花束i必须放在花束j左边的花瓶中。每个花瓶只能放一束花。如果花瓶的数目大于花束的数目，则多余的花瓶空置。54每一个花瓶都具有各自的特点。因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果，并以一美学值(一个整数)来表示，空置花瓶的美学值为零。为取得最佳美学效果，必须在保持花束顺序的前提下，使花束的摆放取得最大的美学值。请求出具有最大美学值的一种摆放方式。552、解题思路状态表示法一：设A(i,j)表示第i种花束摆在第j个花瓶中获得的美学值。S(i,k)表示第i种花束摆在第k个花瓶中时(k≥i)，前i种花束能够获得的最大美学值(之和)。这样，原问题的最优值可通过计算max{S(F,k)|F≤k≤V}获得。下面分析这种状态表示法描述问题的方式是否具备了用动态规划求解的基本要素。56最优子结构性质：对满足F≤k≤V的k，设T(F,k)是达到最优值S(F,k)的一种最佳摆放方式，其中，第F-1种花束摆在第j个花瓶中(j<k)，则T(F,k)中前F-1种花束的摆放方式获得的最大美学值为S(F-1,j)。故对每个满足F≤k≤V的k，计算S(F,k)的问题具有最优子结构性质。递归方程：57在计算S(i-1,k-1)时，已经计算出了S(i-1,j)，i-1≤j≤k-2及其max{S(i-1,j)|i-1≤j≤k-2}。因此，计算S(i,k)时，只要将S(i-1,k-1)与max{S(i-1,j)|i-1≤j≤k-2}进行比较即可求得，即子问题重叠性质。这样做可大大减少计算量。58状态表示法二：设S[i,k]表示第i种花束摆在第k个之前(包括第k个)的任意某个花瓶中，前i种花束能够获得的最大美学值(之和)。这样，原问题的最优值即为S[F,V]。这比前一个表示法更直接。59容易验证，计算S[F,V]的问题具有最优子结构性质。递归方程为：S[i,k]=max{S[i-1,k-1]+A(i,k),S[i,k-1]},i>1,k>i初始条件为：S[1,1]=A[1,1]S[1,k]=max{A(1,k),S[1,k-1]},k>1S[i,i]=S[i-1,i-1]+A(i,i),i>1603.3最长公共子序列子序列定义若给定序列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}的子序列，相应的递增下标序列为{2，3，5，7}。例：两个DNA序列S1=ACCGGTCGAGTGCGCGGAAGCCGGCCGAAS2=GTCGTTCGGAATGCCGTTGCTCTGTAAALCS=GTCGTCGGAAGCCGGCCGAA6162两个序列的公共子序列定义给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。问题给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。63定理：(一个LCS的最优子结构)设序列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)若xm≠yn且zk≠xm，则Z是xm-1和Y的最长公共子序列。(3)若xm≠yn且zk≠yn，则Z是X和yn-1的最长公共子序列。2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。1、最长公共子序列的结构6465662、子问题的递归结构将X和Y的LCS分解为2种情况：如xm=yn，找Xm-1和Yn-1的LCS；//解一个子问题如xm≠yn，找Xm-1和Y的LCS；找X和Yn-1的LCS；//解两个子问题取两者中的最大的；67用c[i][j]记录序列Xi和Yj的最长公共子序列的长度。Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。c[i][j]的递归方程：当i=0或j=0时，空序列是Xi和Yj的最长公共子序列，C[i][j]=0。68693、计算最优值voidLCSLength(intm，intn，char*x，char*y，int**c，int**b){inti，j;for(i=1;i<=m;i++)c[i][0]=0;for(i=1;i<=n;i++)c[0][i]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}}070过程LCSLength以两个序列x、y为输入，它把c[i,j]的值填入一个按行计算表项的表c[0..m,0..n]中，并维护表b[1..m,1..n]以简化最优解的构造。c[0..m,0..n]//存放最优解值，计算时行优先b[1..m,1..n]//解矩阵，存放构造最优解信息b[i,j]指向一个表项，对应于在计算c[i,j]时所选择的最优子问题的解。程序最后返回b和c。c[m,n]包含X和Y的一个LCS的长度。71由于在所考虑的子问题空间中，总共有θ(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。724、构造最长公共子序列构造最长公共子序列voidLCS(inti,intj,char*x,int**b){if(i==0||j==0)return;if(b[i][j]==1){LCS(i-1,j-1,x,b);cout<<x[i];}elseif(b[i][j]==2)LCS(i-1,j,x,b);elseLCS(i,j-1,x,b);}说明当b[i,j]=1时，即xi=yj是LCS的一个元素；时间复杂度：θ(m+n)73构造解时，从b[m,n]出发，上溯至i=0或j=0，上溯过程中，当b[i,j]＝1时打印出xi或yj74例：X=<A,B,C,B,D,A,B>，Y=<B,D,C,A,B,A>最优解：BCAB或BCBA或BADB755、算法的改进在算法LCSLength和LCS中，可进一步将数组b省去。c[i][j]的值仅由c[i-1][j-1]，c[i-1][j]和c[i][j-1]这3个数组元素的值所确定。对于给定的数组元素c[i][j]，可以不借助于数组b而仅借助于c本身在O(1)时间内确定c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一个值所确定的。76如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。计算c[i][j]时，只用到数组c的第i行和第i-1行。只用2行的数组空间就可计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n))。773.4最大子段和问题给定由n个整数(可能为负整数)组成的序列a1,a2,…,an，求该序列形如的子段和的最大值。当所有整数均为负数时定义其最大子段和为0。依此定义，所求的最优值为78例：整数序列(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2)最大子段和为：791、最大子段和问题的简单算法简单算法数组a[]存储给定的n个整数时间复杂度为O(n3)80改进对k循环可以省略改进后的算法时间复杂度为O(n2)812、最大子段和问题的分治算法将a[1:n]分为长度相等的两段a[1:n/2]和a[n/2+1:n]，分别对两区段求最大子段和，则a[1:n]的最大子段和有三种情形：a[1:n]的最大子段和与a[1:n/2]的最大子段和相同a[1:n]的最大子段和与a[n/2:n]的最大子段和相同a[1:n]的最大子段和为对①②可递归求解对③可知a[n/2]、a[n/2+1]一定在最大和子段中在a[1:n/2]中计算，在a[n/2+1:n]中计算，s1+s2是该情况下的最大值。intMaxSubSum(int*a,intleft,intright){//返回最大子段和intsum=0;if(left==right)sum=a[left]>0?a[left]:0;else{intcenter=(left+right)/2;intleftsum=MaxSubSum(a,left,center);intrightsum=MaxSubSum(a,center+1,right);ints1=0;intlefts=0;for(inti=center;i>=left;i--){lefts+=a[i];if(lefts>s1)s1=lefts;}//forintMaxSum(intn,int**a){returnMaxSubSum(a,1,n);}ints2=0;intrights=0;for(inti=center+1;i<=right;i++){rights+=a[i];if(rights>s2)s2=rights;}//forsum=s1+s2;if(sum<leftsum)sum=leftsum;if(sum<rightsum)sum=rightsum;}//ifreturnsum;}//end83复杂度分析843、最大子段和问题的动态规划算法描述最优解的结构子问题定义：考虑所有下标以j结束的最大子段和b[j]，即原问题与子问题的关系：85递归定义最优解的值

b[j]=max{b[j-1]+a[j],a[j]},1≤j≤n86求最大子段和的动态规划算法intMaxSum(intn,int*a){intsum=0,b=0;

//sum存储当前最大的b[j],b存储当前b[j]for(inti=1;i<=n;i++){if(b>0)b+=a[i];elseb=a[i];//b=0if(b>sum)sum=b;}returnsum;}874、最大子段和问题与动态规划算法的推广最大子矩阵和问题给定一个m行n列的整数矩阵A，试求矩阵A的一个子矩阵，使其各元素之和为最大。二维数组a[1:m][1:n]表示给定m行n列的整数矩阵。子数组a[i1:i2][j1:j2]表示左上角和右下角行列坐标分别为(i1,j1)和(i2,j2)的子矩阵。各元素之和最大子矩阵和问题的最优值为88最大m子段和问题给定由n个整数（可能为负整数）组成的序列a1,a2,…,an，以及一个正整数m，要求确定序列a1,a2,…,an的m个不相交子段，使这m个子段的总和达到最大。设b(i,j)表示数组a的前j项中i个子段和的最大值，且第i个子段含a[j]。所求的最优值为。89计算b(i,j)的递归式为初始时，903.5多段图规划问题描述多段图G=(V,E)是一个有向图，且具有以下特征：划分为k≥2个不相交的集合Vi,1≤i≤k;V1和Vk分别只有一个结点s(源点)和t(汇点)；若<u,v>∈E(G)，u∈Vi，则v∈Vi+1,边上成本记c(u,v)；若<u,v>不属于E(G)，边上成本记c(u,v)=∞。求由s到t的最小成本路径。91例：一个5-段图求从s到t的最短路径。92多段图问题满足最优性原理设s,…,vip,…,viq,…,t是一条由s到t的最短路径，则vip,…,viq,…,t也是由vip到t的最短路径。(反证即可)递归式推导设cost(i,j)是Vi中结点vj到汇点t的最小成本路径的成本，递归式为：93计算过程(以5-段图为例)cost(4,9)=4,cost(4,10)=2,cost(4,11)=∞cost(3,6)=7,cost(3,7)=5,cost(3,8)=7cost(2,2)=7,cost(2,3)=9,cost(2,4)=18,cost(2,5)=15cost(1,1)=min{9+cost(2,2),7+cost(2,3),3+cost(2,4),2+cost(2,5)}=16构造解：解1(1,2,7,10,12)，解2(1,3,6,10,12)94953.60-1背包问题问题描述给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?960-1背包问题是一个特殊的整数规划问题。求(x1,x2,…,xn)使目标函数最大，其中c>0,wi>0,vi>0,1≤i≤n0-1背包问题Knapsack(1,n,c)97例：w=(w1,w2,w3)=(2,3,4)v=(v1,v2,v3)=(2,3,4)求Knapsack(1,3,6)取x=(1,0,1)时，Knapsack(1,3,6)=(v1x1+v2x2+v3x3)=1*1+2*0+5*1=6最大用穷举法求解，时间复杂度为O(n2n)981、最优子结构性质证明：(反证法)设(y1,y2,…,yn)是Knapsack(1,n,c)的一个最优解，则(y2,…,yn)是Knapsack(2,n,c-w1y1)子问题的一个最优解。若不然，设(z2,…,zn)是Knapsack(2,n,c-w1y1)的最优解，因此有说明(y1,z2,…,zn)是Knap(1,n,c)的一个更优解，矛盾。0-1背包问题Knapsack(1,n,c)满足最优性原理992、递归关系设所给0-1背包问题的子问题记为Knapsack(i,n,j)，j≤c(假设c,wi取整数)Knapsack(i,n,j)的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。注：子问题的背包容量j在不断地发生变化100由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下：临界条件说明：当j＜wi时，只有xi=0，则m(i,j)=m(i+1,j)当j≥wi时，取xi=0时，为m(i+1,j)取xi=1时，为m(i+1,j-wi)+vi3、算法描述voidKnapsack(Type*v,int*w,intc,intn,Type**m){//m[1][c]为最优值intjMax=min(w[n]-1,c);//j≤jMax,即0≤j＜wn;j>jMax,即j≥wnfor(intj=0;i<=jMax;j++)m[n][j]=0;//0≤j<wn’for(intj=w[n];i<=c;j++)m[n][j]=v[n];//j≥wn’for(inti=n-1;i>1;i--){//i>1表示对i=1暂不处理i=1时只需求m[1][c]jMax=min(w[i]-1,c);for(intj=0;j<=jMax;j++)//0≤j＜wi’m[i][j]=m[i+1][j];for(intj=w[i];j<=c;j++)//j≥wi’m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);}m[1][c]=m[2][c];if(c>=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);}102voidTraceback(Type**m,int*w,intc,intn,int*x){//输出解X[]for(inti=1;i<n;i++)if(m[i][c]==m[i+1][c])x[i]=0;else{x[i]=1;c-=w[i];}x[n]=(m[n][c])?1:0;}1034、计算复杂性分析算法复杂度分析从m(i，j)的递归式容易看出，算法需要O(nc)计算时间。当背包容量c很大时，算法需要的计算时间较多。例：当c>2n时，算法需要Ω(n2n)计算时间。104由m(i,j)的递归式容易证明，在一般情况下，对每一个确定的i(1≤i≤n)，函数m(i,j)是关于变量j的阶梯状单调不减函数。跳跃点是这一类函数的描述特征。一般情况下，函数m(i,j)由其全部跳跃点唯一确定。105对每一个确定的i(1≤i≤n)，用一个表p[i]存储函数m(i，j)的全部跳跃点。表p[i]可依计算m(