【教学课件】第3章动态规划.ppt

第3章 动态规划,3.1 动态规划法的基本概念3.2 动态规划法的应用专题,动态规划,动态规划（Dynamic Programming）20世纪50年代美国数学家贝尔曼（Richard Bellman)为研究最优控制问题而提出的。动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。应用：动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。,3.1 动态规划的基本概念,3.1.1 什么是动态规划例1：计算斐波那契数3.1.2 动态规划的求解方法例2：多段图的最短路径问题例3：街道问题例4：数字三角形问题3.1.3 动态规划小结3.1.4 矩阵连乘问题,3.1.1 什么是动态规划,动态规划是求解包含重叠子问题的最优化方法基本思想：将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解（注意：不是简单分而治之）。,例1：计算斐波那契数,方法一：分治法long fib(int n)long p;if(n=0|n=1)return n;else p=fib(n-1)+fib(n-2);return p;,法1：分治法,计算斐波那契数的过程（n=5）,冗余计算,法2：动态规划法,分析：计算f(n)是以计算它的两个重叠子问题 f(n1)和f(n2)的形式来表达的，所以，可以设计一张表填入n1个f(n)的值。动态规划法求解斐波那契数f(9)的填表过程,3.1.1 什么是动态规划,动态规划法的设计思想：将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段。一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中。将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。,动态规划与分治法的异同点,相同点：动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题或分为若干级（阶段），然后顺序求出各个子问题。区别：动态规划法：经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。分治法：经分解得到的子问题往往是互相独立的，在用分治法求解时，有些子问题被重复计算了许多次。,3.1.1 什么是动态规划,动态规划的基本要素重叠子问题性质能够分解为相互重叠的若干子问题；在用分治算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题可能被重复计算多次。动态规划算法利用此性质，对每个子问题只计算一次，然后将其结果保存起来以便高效重用。最优化子结构性质若问题的最优解所包含的子问题的解也是最优的，则称该问题具有最优子结构性质（即满足最优化原理）,3.1.2 动态规划的求解方法,求解方法1.把问题分成许多个子问题（一般地每个子问题是互相关联和影响的）2.依次研究逐个问题的决策。常见的处理方法：向前处理法(forward approach)：向后处理法(backward approach),例2：多段图的最短路径,多段图,例2：多段图的最短路径,多段图多段图G(V,E)是一个有向图。它有如下特点：图中结点被分成 k 2个不相交的集合Vi（1 i k）；其中：V1和Vk 分别只有一个结点s(源点)和t(终点)。图中的边(u,v)有如下性质：若u Vi,则v Vi+1,（1 i k-1）。多段图问题求多段图中由s（源点）到t（终点）的最小成本路径。,例2：多段图的最短路径,例如：,例2:多段图的最短路径,1.分解最优解的结构不难说明多段图问题具有最优子结构性质。2.建立递归关系(1)向前处理法设c为图的代价矩阵设p(i,j)是一条从集合Vi中的结点j到终点t的最小成本路径；cost(i,j)是这条路径的成本。,例2:多段图的最短路径,显然有：,初始时，,例2:多段图的最短路径,3.计算最优值,V1 V2 V3 V4 V5,例2:多段图的最短路径,4.根据计算最优值时得到的信息，构造最优解。,例2:多段图的最短路径,当然也可以采用：向后处理法设BP(i,j)是一条从源点s到集合Vi中的结点j的最小成本路径;Bcost(i,j)是这条路径的成本。,例2:多段图的最短路径,显然有：,初始时，,例2:多段图的最短路径,V1 V2 V3 V4 V5,练习,最短路径：03589，长度为16。,应用实例,路径规划车辆卫星定位系统路径规划：基于具有拓扑结构的道路网络，在车辆驶前或行驶过程中寻找车辆从起始点到目的地的最佳行驶路线的过程，它是多段图最短路径问题。,例3：街道问题,问题描述：在一个如下图所示的正方形组成的矩形地图中中找出从左下角到右上角的最短路径，每步只能向右方或上方走。,状态转移方程（动态规划函数）：,例4:数字三角形问题,数字三角形（P90）问题描述分析穷举法动态规划法,动态规划函数,3.1.3 动态规划小结,1.动态规划基本步骤找出最优解的性质，并刻划其结构特征递归地定义最优值计算最优值根据计算最优值时得到的信息，构造最优解,3.1.3 动态规划小结,2.应用动态规划法要注意：阶段的划分是关键最优化原理应在子问题求解中体现,3.1.3 动态规划小结,动态规划与分治法 相同点不同点动态规划较之于穷举法的优势大大减少了计算量丰富了计算结果,矩阵连乘问题,两个矩阵相乘若A是pq矩阵，B是qr矩阵,则矩阵相乘运算共要：pqr次乘法.矩阵连乘给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，考察这n个矩阵的连乘积 A1 A2 An问题：如何确定最优计算顺序？,3.1.4 矩阵连乘问题,例1：设有三个矩阵A1,A2,A3，它们的维数分别是 A1 10100，A2 1005，A3 550，则：则：（1）计算(A1A2)A3)共需要：10*100*5+10*5*507500 乘法（2）计算(A1(A2A3)共需要100*5*50+10*100*5075000 乘法,3.1.4 矩阵连乘问题,例2：设有四个矩阵ABCD，它们的维数分别是：,16000 1050036000 8750034500,3.1.4 矩阵连乘问题,因此：由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为：单个矩阵是完全加括号的；矩阵连乘积 A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积 B和C 的乘积并加括号，即A（B C）。,矩阵连乘问题,问题提出：给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，考察这n个矩阵的连乘积A1 A2 An如何确定计算矩阵连乘积的计算次序（即确定矩阵的完全加括号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少？,方法1：穷举法,穷举法基本思想列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。特点：计算量大,方法1：穷举法,分析对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1An)可以得到关于P(n)的递推式如下：,方法2：动态规划法,1.分析最优解的结构引入记号：将矩阵连乘积Ai Ai+1 Aj 记为Ai:j。特征：计算A1:n的最优次序所包含的计算矩阵子链 A1:k和Ak+1:n的次序也是最优的。即：矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。,2.建立递归关系计算Ai:j所需要的最少数乘次数mij，则原问题的最优值为m1n。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，ikj，则其相应完全加括号方式为(Ai Ai+1 Ak)(Ak+1 Ak+2 Aj)则总的计算量 Ai:k的计算量 Ak+1:j的计算量 Ai:kAk+1:j 的计算量。,方法2：动态规划法,2.建立递归关系可以递归地定义mij为：,这里 的维数为,方法2：动态规划法,方法2：动态规划法,3.计算最优值对于1ijn不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数为：,4.构造最优解,一个实例,计算A1 A2 A3 A4 A5 A6的最优次序。,即：,例如：计算A1 A2 A3 A4 A5 A6的最优次序。,故：计算A1 A2 A3 A4 A5 A6的最优次序为,void 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(int k=i+1;k j;k+)int t=mik+mk+1j+pi-1*pk*pj;if(t mij)mij=t;sij=k;/for k/for i,计算最优值的算法描述,构造最优解的算法描述,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;,算法复杂度分析：时间复杂性算法matrixChain的主要计算量取决于算法中对r，i和k的3重循环，因此T(n)O(n3)。空间复杂性S(n)O(n2)。,方法3：递归分治求解,算法描述：（P54）int RecurMatrix(int i,int j)if(i=j)return 0;u=RecurMatrix(i,i)+RecurMatrix(i+1,j)+pi-1*pi*pj;sij=i;for(k=i+1;kj;k+)t=RecurMatrix(i,k)+RecurMatrix(k+1,j)+pi-1*pk*pj;if(tu)u=t;sij=k;/for return u;,(Ai Ai+1 Ak)(Ak+1 Ak+2 Aj),分析：,方法3：递归分治求解,小结,1.动态规划算法的基本要素最优子结构最优子结构是问题能用动态规划算法求解的前提。重叠子问题每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。（自底向上求解）通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。,小结,2.分治法自顶向下求解对重叠的子问题被反复计算多次，效率低。3.备忘录方法备忘录方法的控制结构与直接递归方法的控制结构相同（自顶向下）但备忘录方法为每个解过的子问题建立了备忘录，以备需要时查看，避免了相同子问题的重复求解。,小结,例如：int LookupChain(int i，int j)if(mij 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;,3.2 动态规划法的应用专题,图问题中的动态规划法组合问题中的动态规划法几何问题中的动态规划法查找问题中的动态规划法,应用专题一,图问题中的动态规划法多段图的最短路径问题每对结点间的最短路径TSP问题,每对结点间的最短路径,问题提出：G=(V,E)是一个有n个结点的有向图，C是G的成本邻接矩阵。其中C(i,i)=0,C(i,j)=(当边E)。要求：将每对结点间的最短路径值存入矩阵A：A(i,j)：结点i到结点j的最短路径长度。,每对结点间的最短路径,1.问题的最优子结构性质假设i到j的最短路径有一个中间结点k，则由i到k和k到j的子路径分别是i到k和k到j的最短路径，否则i到j的路径就不具有最短路径。故：该问题具备最优子结构性质。,每对结点间的最短路径,2.建立递归关系用符号Ak(i,j)表示从i到 j并且不经过比序号k还大的结点的最短路径长度，则显然i到k和k到j两条最短路径都不可能有比序号k1还大的中间结点。,3.计算最优值依次计算A1,A2,An 构造最优值An就记录了图中每对结点间的最短路径长度。,每对结点间的最短路径,例：求下图的各个结点间的最短路径长度。,每对结点间的最短路径,每对结点间的最短路径,每对结点间的最短路径,void All-paths(int n,int*cost,int*A)/cost-图的成本邻接矩阵，A-距离矩阵 for(int i=1;i=n;i+)/初始化Aij for(int j=1;j=n;j+)Aij=costij;for(int k=1;k=n;k+)for(int i=1;i=n;i+)for(int j=1;j=n;j+)Aij=min(Aij,Aik+Akj);,TSP问题,问题描述：旅行商问题（Traveling Salesman Problem）问题抽象：可以用结点表示城市，城市间的交通路线用边表示，而城市间的交通线路距离可用附加于边的权表示。这样：上述问题可以归结为寻找一条权的总和为最短的哈密尔顿回路的问题。,TSP问题,分析：各个城市间的距离可以用代价矩阵来表示。,TSP问题,1.最优子结构性质设s,s1,s2,sp,s是从s出发的一条路径长度最短的简单回路，假设从s到下一个城市s1已经求出，则问题转化为求从s1到s的最短路径，显然s1,s2,sp,s一定构成一条从s1到s的最短路径。即TSP问题具备最优子结构性质。,TSP问题,2.定义递归关系假设从顶点s出发，令d(i,V)表示从顶点i出发经过V中各个顶点一次且仅一次，最后回到出发点s的最短路径长度，开始时，i s，VV s，于是，TSP问题的动态规划函数为：,TSP问题,3.计算最优值,（1）从城市0出发经城市1、2、3然后回到城市0的最短路径长度是：d(0,1,2,3)=minc01+d(1,2,3),c02+d(2,1,3),c03+d(3,1,2)这是最后一个阶段的决策。这一阶段的决策又依赖于下面的计算结果。,TSP问题,3.计算最优值,（2）d(1,2,3)=minc12+d(2,3),c13+d(3,2)d(2,1,3)=minc21+d(1,3),c23+d(3,1)d(3,1,2)=minc31+d(1,2),c32+d(2,1)这一阶段的决策又依赖于下面的计算结果。,TSP问题,3.计算最优值,（3）d(1,2)=c12+d(2,)d(2,3)=c23+d(3,)d(3,2)=c32+d(2,)d(1,3)=c13+d(3,)d(2,1)=c21+d(1,)d(3,1)=c31+d(1,)这一阶段的决策又依赖于下面的计算结果：,TSP问题,3.计算最优值,（4）而下式可以直接获得（括号中是该决策引起的状态转移）：d(1,)=c10=5(10)d(2,)=c20=6(20)d(3,)=c30=3(30)再往前推,TSP问题,3.计算最优值,d(1,2)=c12+d(2,)=2+6=8(12)d(2,3)=c23+d(3,)=2+3=5(23)d(3,2)=c32+d(2,)=5+6=11(32)d(1,3)=c13+d(3,)=3+3=7(13)d(2,1)=c21+d(1,)=4+5=9(21)d(3,1)=c31+d(1,)=7+5=11(31)再往前推,TSP问题,3.计算最优值,d(1,2,3)=minc12+d(2,3),c13+d(3,2)=min2+5,3+11=7(12)d(2,1,3)=minc21+d(1,3),c23+d(3,1)=min4+6,2+12=10(21)d(3,1,2)=minc31+d(1,2),c32+d(2,1)=min7+8,5+9=14(32),TSP问题,3.计算最优值,则：从城市0出发经城市1、2、3然后回到城市0的最短路径长度是：d(0,1,2,3)=minc01+d(1,2,3),c02+d(2,1,3),c03+d(3,1,2)=min3+7,6+10,7+14=10(01),4.构造最优解从顶点0出发的TSP问题的最短路径长度为10，路径是01230。,TSP问题,动态规划法求解TSP问题的填表过程dij表示从顶点i经过子集Vj中的顶点一次且仅一次，最后回到出发点0的最短路径长度。,TSP问题,TSP问题求解过程示意图,TSP问题的算法描述,1for(i=1;in;i+)/初始化第0列 di0=ci0;2for(j=1;j2n-1-1;j+)for(i=1;in;i+)/依次进行第i次迭代 if(子集Vj中不包含i)对Vj中的每个元素k，计算dij=min(cik+dkj-1);3对V2n-1-1中的每一个元素k，计算d02n-1-1=min(c0k+dk2n-1-2);4输出最短路径长度d02n-1-1;,应用专题二,组合问题中的动态规划法最大子段和问题最长单调递增子序列问题最长公共子序列问题0/1背包问题,最大子段和问题,问题提出：给定由n个整数（可能为负数）组成的序列：a1,a2,an,求该序列的最大子段和。当所有整数均为负数，定义其最大子段和为0。依其定义，所求的最优值为：,最大子段和问题,动态规划算法,最大子段和问题,算法描述：int maxsum(int n,int*a)sum=0;b=0;for(i=1;i0)b+=ai;else b=ai;if(bsum)sum=b;return sum;,算法时间复杂性：T(n)=O(n)S(n)=O(1),最大子段和问题,算法描述：int maxsum(int n,int*a)sum=0;b0=0;for(i=1;i0)bi=bi-1+ai;else bi=ai;if(bisum)sum=bi;return sum;,算法复杂性：T(n)=O(n)S(n)=O(n),最大子段和问题,应用举例：最佳游览路线问题,最长单调递增子序列问题,问题描述：求最长单调递增子序列问题。例如：1 23 4 5 6 7 8 9 10 a:318714101223411624b:6353432121c:375767881010,最长公共子序列问题,子序列与公共子序列：一个给定序列的子序列序列X和Y的公共子序列问题提出：给定2个序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最长公共子序列。,最长公共子序列问题,例如：对xyzyxzxz和xzyxxyzx两个序列xxx为长度为3的公共子序列，xzyz为长度为4的公共子序列。xzyxxz为长度为6的最长公共子序列。,最长公共子序列问题,应用：文本相似性测试在遗传学中，两个串对应链条DNA链，它们可能来自两个个体，若它们对应的DNA序列有一条长的公共子序列，则认为它们在遗传上是相关的。在软件工程应用中，两个串可能来自同一个程序的源代码的两个版本，希望确定两个版本之间有哪些变化。搜索引擎中的数据收集系统(也称web蜘蛛或爬虫)必定能区分相似的web页面，避免不必要的web页面请求。Unin/linux中提供diff程序，用于比较文本文件。,最长公共子序列问题,问题分析：若A的长度为m，若B的长度为n，则A和B的子序列个数分别为：,最长公共子序列问题,穷举法耗时太多，不可取，共需要进行串比较：,分治法此问题不可能简单地分解成几个独立的子问题，也不能用分治法来解。动态规划法,最长公共子序列问题,最长公共子序列的最优子结构性质设序列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)若xmyn且zkxm，则Z是xm-1和Y的最长公共子序列。(3)若xmyn且zkyn，则Z是X和yn-1的最长公共子序列。,由此可见：两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。,最长公共子序列问题,二、子问题的递归结构,最长公共子序列问题,三、计算最优值第一阶段:计算X1和Yj的最长公共子序列的长度c1j。第二阶段:计算X2和Yj的最长公共子序列的长度c2j。第m阶段:计算Xm和Yj的最长公共子序列的长度cmj。(1jn)注：第m阶段的cmn 就是序列Xm和Yn的最长公共子序列的长度。,最长公共子序列问题,int LCSLegth(int m,int n,char*x,char*y,int*c,int*b)for(j=0;j=cij-1)cij=ci-1j;bij=2;else cij=cij-1;bij=3;,例如：,最长公共子序列问题,四、构造最长公共子序列设cmn=k，则Xm与Yn的最长公共子序列：z1z2zk，令i=m;j=n，则搜索过程如下：若bi,j=1，则xi=yj，由性质1知：zk=xi，下一搜索方向为ci-1,j-1;若bi,j=2，则xiyj，且ci-1,jci,j-1，由性质2知：下一搜索方向为ci-1,j;若bi,j=3，则xiyj，且ci-1,jci,j-1，由性质3知：下一搜索方向为ci,j-1;,最长公共子序列问题,得到如下递推关系若bi,j=1，则：zk=xi，i-;j-;k-;若bi,j=2，则：i-;若bi,j=3，则：j-;从i=m,j=n开始搜索，直到i=0或j=0结束，此时得到最长公共子序列z1z2zk。,最长公共子序列问题,参考代码 i=m;j=n;k=cmn;while(i0 输出：z1z2Zcmn。,例如：,最长公共子序列：BCBA,最长公共子序列问题,算法分析：时间复杂性(mn)；空间复杂性(mn)；,0-1背包问题,问题描述,例：n=3,(v1,v2,v3)=(25,24,15),(w1,w2,w3)=(18,15,10),c=20。0-1背包问题的最优解为:(x1,x2,x3)=(1,0,0)。,0-1背包问题,1.0-1背包问题的最优子结构性质设(y1,y2,yn)是所给01问题的一个最优解，则(y2,y3,yn)是下面相应子问题的一个最优解，,0-1背包问题,2.建立递归关系（建立动态规划方程）所给0-1背包问题的子问题为：,令：m(i，j)背包容量为j，可选择物品为i，i+1,n时0_1背包问题的最优值。（0jc）,0-1背包问题,分析（1）边界条件,0-1背包问题,(2)一般形式：,0-1背包问题,即：计算m(i，j)的动态规划函数如下：,0-1背包问题,3.计算最优值第1阶段：确定m(n，j)第2阶段：确定m(n-1，j)第3阶段：确定m(n-2，j)第n阶段：确定m(1，j)(其中m1,c为原问题的最优值)其中：（0jc）4.构造最优解,例如：,考虑如下0-1背包问题:n=3,c=6(v1,v2,v3)=(1,2,5),(w1,w2,w3)=(2,3,4)以下是计算过程：i=3,w3=4,v3=5 m(3,0)=0,m(3,1)=0,m(3,2)=0,m(3,3)=0 m(3,4)=5,m(3,5)=5,m(3,6)=5,i=2,w2=3,v2=2 m(2,0)=m(3,0)=0 m(2,1)=m(3,1)=0 m(2,2)=m(3,2)=0 m(2,3)=maxm(3,3),m(3,0)+2=2 m(2,4)=maxm(3,4),m(3,1)+2=5 m(2,5)=maxm(3,5),m(3,2)+2=5 m(2,6)=maxm(3,6),m(3,3)+2=5,i=1,w1=2,v1=1 m(1,0)=m(2,0)=0,m(1,1)=m(2,1)=0 m(1,2)=maxm(2,2),m(2,0)+1=1 m(1,3)=maxm(2,3),m(2,1)+1=2 m(1,4)=maxm(2,4),m(2,2)+1=5 m(1,5)=maxm(2,5),m(2,3)+1=5 m(1,6)=maxm(2,6),m(2,4)+1=6,构造最优解：由于m(1,6)m(2,6)放物品1，x1=1,c=cw1=4 比较m(2,4)与m(3,4)是否相等不放物品2，x2=0 由于m(3,4)0 放物品3，x3=1 即：最优解为（1，0，1）,算法描述,void Knapsack(int*v,int*w,int*x,int c,int n,int*m)/(1)初始化边界条件 for(j=0;j=c;j+)if(jwn)mnj=0;/不可装入第n件物品 else mnj=vn;/可装入第n件物品,算法描述,/(2)向前处理,计算mijfor(i=n-1;i=1;i-)for(j=0;j wi;j+)/0jwi mij=mi+1j;/不放入第i件物品 for(j=wi;j=c;j+)/jwi,可放入第i件物品 mij=max(mi+1j,mi+1j-wi+vi);,算法描述,/(3)构造最优解for(i=1;i n;i+)if(mic=mi+1c)xi=0;else xi=1;c=wi;xn=(mnc)?1:0;,该算法有两个弱点：算法要求物品重量wi为整数；从m(i，j)的递归式容易看出，算法需要O(nc)计算时间。当背包容量c很大时，算法需要的计算时间较多。,思考（方法2）：0-1背包问题,1.0-1背包问题的最优子结构性质设(y1,y2,yn)是所给01问题的一个最优解，则(y1,y2,yn-1)是下面相应子问题的一个最优解。,0-1背包问题,2.建立递归关系（建立动态规划方程）所给0-1背包问题的子问题为：,令：m(i，j)背包容量为j，可选择物品为1,2,i时0_1背包问题的最优值。（0jc）,0-1背包问题,分析（1）边界条件,0-1背包问题,(2)一般形式：,0-1背包问题,即：计算m(i，j)的动态规划函数如下：,0-1背包问题,3.计算最优值第1阶段：确定m(1，j)第2阶段：确定m(2，j)第3阶段：确定m(3，j)第n阶段：确定m(n，j)(其中m（n,c）为原问题的最优值)其中：（0jc）4.构造最优解,例如：,考虑如下0-1背包问题:n=3,c=6(v1,v2,v3)=(1,2,5),(w1,w2,w3)=(2,3,4)练习：填表情况及求解最优解；写出按上述方法求解0/1背包的算法描述。,填表情况及最优解的构造,应用专题三,查找问题中的动态规划法最优二叉查找树模糊查找（选讲）,最优二叉查找树,问题描述：最优二叉查找树（Optimal Binary Search Trees）以n个记录r1,r2,rn构成的二叉查找树中具有最少平均比较次数的二叉查找树。,分析判定树折半查找n个结点的深度为log2(n1)1。折半查找假定：所有元素的查找概率是相等的。如果查找概率不相等，则不是最优的。,最优二叉查找树,例如：已知：集合A,B,C,D的查找概率是0.1,0.2,0.4,0.3，问：二叉查找树的平均比较次数分别为多少？,最优二叉查找树,一、最优二叉查找树满足最优性原理,最优二叉查找树,二、递归地定义最优值设：T(i,j)是由记录ri,rj(1ijn)构成的最优二叉查找树C(i,j)是最优二叉树的平均比较次数（C(1,n)为原问题的解）。考虑从ri,rj中选择一个记录rk作为二叉查找树的根结点，可以得到如下关系：,最优二叉查找树,可以得到如下动态规划函数：,三、计算最优值按对角线逐条计算每一个C(i,j)和R(i,j)，得到最终表。,四、构造最优解C(1,4)1.7 R(1,4)=3(元素r3为根)C(1,2)0.4 R(1,2)=2(元素r2为左子树根)得到如下最优二叉查找树,应用专题四,几何问题中的动态规划法（选讲）最优三角剖分,本章小结：,动态规划法的基本要素求解过程分析最优子结构建立递归关系计算最优值构造最优解几个典型示例,本章小结：,最优化问题每个最优化问题都包含一组限制条件和一个优化函数，符合限制条件的问题求解方案称为可行解，使优化函数取得最佳值的可行解称为最优解。,本章小结：,最优化问题的求解方法：穷举法动态规划法贪心法搜索法,