《算法分析与设计动态规划ppt课件.ppt》由会员分享，可在线阅读，更多相关《算法分析与设计动态规划ppt课件.ppt（91页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、算法分析与设计动态规划ppt课件 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望第四章第四章 动态规划动态规划什么是动态规划什么是动态规划多段图多段图最优二分检索树最优二分检索树0/1背包问题背包问题可靠性设计可靠性设计货郎担问题货郎担问题2在实际生活中，有这么一类问题，它们的活在实际生活中，有这么一类问题，它们的活动过程可以分为若干个阶段，而且在任一阶动过程可以分为若干个阶段，而且在任一阶段后的行为都依赖于段后的行为都依赖于i 阶段的过程状态，而阶段的过程状态，
2、而与与i 阶段之前的过程是如何达到这种状态的阶段之前的过程是如何达到这种状态的方式无关，这样的过程就构成了一个方式无关，这样的过程就构成了一个多阶段多阶段决策过程决策过程。根据这类问题的多阶段决策的特性，提出了根据这类问题的多阶段决策的特性，提出了解决这类问题的解决这类问题的“最优性原理最优性原理”，从而创建，从而创建了最优化问题的一种新的算法设计方法了最优化问题的一种新的算法设计方法动态规划动态规划。4.1 一般方法一般方法3在多阶段决策过程的每一个阶段，都可在多阶段决策过程的每一个阶段，都可能有多种选择的决策，但必须从中选取能有多种选择的决策，但必须从中选取一种决策。一旦各种阶段的决策选定
3、之一种决策。一旦各种阶段的决策选定之后，就构成了解决这一问题的一个决策后，就构成了解决这一问题的一个决策序列。决策序列不同，导致的问题结果序列。决策序列不同，导致的问题结果也不同。也不同。动态规划的目标就是要在所有容许选择动态规划的目标就是要在所有容许选择的决策序列中选取一个会获得问题最优的决策序列中选取一个会获得问题最优解的决策序列，即解的决策序列，即最优决策序列最优决策序列。什么是动态规划4最优性原理最优性原理最优性原理最优性原理(Principle of Optimality)过程的最优决策序列过程的最优决策序列具有如下性质：无论过程的具有如下性质：无论过程的初始状态和初始决策是什么，其
4、余的决策都必须相对初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。于初始决策所产生的状态构成一个最优决策序列。利用动态规划求解问题的前提利用动态规划求解问题的前提 1)证明问题满足最优性原理证明问题满足最优性原理 如果对所求解问题证明满足最优性原理，则说明如果对所求解问题证明满足最优性原理，则说明用动态规划方法有可能解决该问题用动态规划方法有可能解决该问题 2)获得问题状态的递推关系式获得问题状态的递推关系式 获得各阶段间的递推关系式是解决问题的关键。获得各阶段间的递推关系式是解决问题的关键。5多段图问题多段图问题多段图问题多段图问题123458761
5、110912st97324227111118654356524V1V2V3V4V56多段图问题多段图问题多段图多段图G(V,E)是是个有向图。它具有如下特性：个有向图。它具有如下特性：图中的结点被划分成图中的结点被划分成k 2个不相交的集合个不相交的集合Vi ,1ik,ik,其中其中V1和和Vk分别只有一个结点分别只有一个结点s(源源点点)和和 t(汇点汇点)。图中所有的边图中所有的边均具有如下性质：若均具有如下性质：若uVi，则，则v Vi+1,1ik,ik,且每条边且每条边均附有均附有成本成本c(u,v)。从从s到到t的一条路径成本是这条路径上边的成本的一条路径成本是这条路径上边的成本和。
6、和。多段图问题多段图问题(multistage graph problem)是求由是求由s到到t的的最小成本路径最小成本路径。7多段图问题多段图问题最优性原理对多段图成立最优性原理对多段图成立假设假设s,v2,v3,vk-1,t是一条由是一条由s到到t的的最短路径最短路径再假设从源点再假设从源点s开始，已作出了到结点开始，已作出了到结点V2的决的决策，因此策，因此V2就是初始决策所产生的状态就是初始决策所产生的状态如果把如果把V2看成是原问题的一个子问题的初始状看成是原问题的一个子问题的初始状态，解决这个子问题就是找出一条由态，解决这个子问题就是找出一条由V2到到t的的最短路径最短路径这条最短
7、路径显然是这条最短路径显然是v2,v3,vk-1,t如果不是，设如果不是，设v2,q3,qk-1,t由由V2到到t的更短的更短路径，则这条路径肯定比路径，则这条路径肯定比v2,v3,vk-1,t路径路径短，这与假设矛盾，因此最优性原理成立短，这与假设矛盾，因此最优性原理成立80/1背包问题背包问题背包问题中的背包问题中的xj限定只能取限定只能取0或或1值，用值，用KNAP(1,j,X)来表示这个问题来表示这个问题效益值背包容量则则0/1背包问题就是背包问题就是KNAP(1,n,M)9最优化决策序列的表示最优化决策序列的表示设设S0是问题的初始状态。假定要作是问题的初始状态。假定要作n次决策次决
8、策xi,1inX1=r1,1,r1,2,r1,pj是是x1的可能决策值的集合，而的可能决策值的集合，而S1,1是在选取决策值是在选取决策值r1,j1以后所产生的状态，以后所产生的状态，1j1p1又设又设F1,j1是相应于状态是相应于状态S1,j1的最优决策序列的最优决策序列则相应于则相应于S0的最优决策序列就是的最优决策序列就是r1,j1 F1,j1|1j1p1中最优的序列，记作中最优的序列，记作如果已作了如果已作了k-1次决策，次决策，1k-1nk-1n。设。设x x1 1,x,xk-1k-1的最优的最优决策值是决策值是r r1 1,.,r,.,rk-1k-1，他们所产生的状态为，他们所产生
9、的状态为S S1 1,S,Sk-1k-110最优化决策序列的表示最优化决策序列的表示又设又设Xk=rk,1,rk,2,rk,pk是是xk的可能值的的可能值的集合。集合。Sk,jk是选取是选取rk,jk决策之后所产生的状决策之后所产生的状态态,1jkpkFk,jk 是相应于是相应于Sk,jk的最优决策序列。的最优决策序列。因此，相应于因此，相应于Sk-1的最优决策序列是的最优决策序列是于是相应于于是相应于S0的最优决策序列为：的最优决策序列为：r1,rk-1,rk,Fk11向前处理法向前处理法(forward approach)从最后阶段开始，以逐步向前递推的方式列出从最后阶段开始，以逐步向前递
10、推的方式列出求前一阶段决策值的递推关系式，即根据求前一阶段决策值的递推关系式，即根据xi+1,xn的那些最优决策序列来列出求取的那些最优决策序列来列出求取xi决决策值的关系式，这就是动态规划的策值的关系式，这就是动态规划的向前处理法向前处理法向后处理方法向后处理方法(backward approach)就是根据就是根据x1,xi-1的那些最优决策序列列出求的那些最优决策序列列出求xi的递推的递推关系式。关系式。多段图的向前处理和向后处理多段图的向前处理和向后处理0/1背包问题的向前处理和向后处理背包问题的向前处理和向后处理124.2 多段图多段图多段图向前处理的算法多段图向前处理的算法设设P(
11、i,j)是一条从是一条从Vi中的节点中的节点j 到汇点到汇点t 的最小的最小成本路径，成本路径，COST(i,j)表示这条路径的成本，表示这条路径的成本，根据向前处理方法有公式根据向前处理方法有公式4.5：13因为，若因为，若 EE成立成立,有有COST(k-1,j)=c(j,t),(k-1,j)=c(j,t),若若 EE不成立，则有不成立，则有COST(k-1,j)=(k-1,j)=，所以，所以可以通过如下步骤解式公式（可以通过如下步骤解式公式（4.54.5），并求出），并求出COST(1,s)。首先对于所有首先对于所有jVk-2，计算，计算COST(k-2,j)，然后对，然后对所有的所有的
12、jVk-3，计算计算，计算计算COST(k-3,j)等等，最后等等，最后计算出计算计算出计算COST(1,s)多段图的多段图的向前处理算法向前处理算法14例子中例子中5段图的段图的实现计算步骤：实现计算步骤：COST(4,9)=4COST(4,10)=2COST(4,11)=5COST(3,6)=min6+COST(4,9),5+COST(4,10)=7COST(3,7)=min4+COST(4,9),3+COST(4,10)=5COST(3,8)=min5+COST(4,10),6+COST(4,11)=7多段图的多段图的向前处理算法向前处理算法15COST(2,2)=min4+COST(3
13、,6),2+COST(3,7),1+COST(3,8)=7COST(2,3)=9COST(2,4)=18COST(2,5)=15COST(1,1)=min9+COST(2,2),7+COST(2,3),3+COST(2,4),2+COST(2,5)=16多段图的多段图的向前处理算法向前处理算法16例子中例子中5段图的实现计算步骤：段图的实现计算步骤：在计算每一个在计算每一个COST(i,j)的同时，记下每个状态的同时，记下每个状态(结点结点j)所做出的决策，设为所做出的决策，设为D(i,j)，则可容易地，则可容易地求出这条最小成本路径。求出这条最小成本路径。D(3,6)=10D(3,7)=10
14、D(3,8)=10D(2,2)=7D(2,3)=6D(2,4)=8D(2,5)=8D(1,1)=2 设这条最小成本路径是设这条最小成本路径是sl,v2,v3,vk-1,t=12。则可得知：则可得知：v2D(1,1)2，v3=D(2,D(1,1)=7 和和v4D(3,D(2,D(1,1)D(3,7)10多段图的多段图的向前处理算法向前处理算法17多段图的多段图的向前处理算法向前处理算法procedure FGRAP(E,k,n,P)real COST(n),integer D(n-1),P(k),r,j,k,nCOST(n)0for jn-1 to 1 by 1 do 设设r是一个这样的结点是一
15、个这样的结点,E且使且使c(j,r)+COST(r)取小值取小值COST(j)c(j,r)+COST(r)D(j)rrepeatP(1)1;P(k)nfor j2 to k-1 doP(j)D(P(j-1)repeatEnd FGRAPH计算出计算出COST(j)的值，的值，并找出一条最小成本并找出一条最小成本路径路径找出最小成本路径找出最小成本路径上的第上的第j个结点个结点18多段图的多段图的向后处理算法向后处理算法向后处理方法向后处理方法(backward approach)就是就是根据根据x1,xi-1的那些最优决策序列列出的那些最优决策序列列出求求xi的递推关系式。的递推关系式。123
16、458761110912st97324227111118654356524V1V2V3V4V519多段图的多段图的向后处理算法向后处理算法设设BP(i,j)是一条由源点是一条由源点s到到Vi中结点中结点j的最的最小成本路径，小成本路径，BCOST(i,j)表示表示BP(i,j)的成的成本本，由向后处理方法得到，由向后处理方法得到公式公式4.6：即由源点即由源点s到到Vi中结点中结点j的最小成本，等于由的最小成本，等于由源点源点s到到Vi-1中任一结点中任一结点l 的最小成本加上的最小成本加上Vi-1中结点中结点l 到到Vi中结点中结点j的边长的边长,所得的所有和所得的所有和中最小的那个值。中最
17、小的那个值。20因为，若因为，若 EE成立成立,BCOST(2,j)=c(1,j),BCOST(2,j)=c(1,j),若若 EE不成立，不成立，则有则有BCOST(2,j)=BCOST(2,j)=，所以可以通过如下步，所以可以通过如下步骤解式公式（骤解式公式（4.64.6），），首先对首先对i3计算计算BCOST，然后对，然后对 i4 计算计算BCOST等，最后等，最后计算出计算出BCOST(k，t)。BCOST(2，2)=9；BCOST(2，3)=7；BCOST(2，4)=3；BCOST(2，5)=2；多段图的多段图的向后处理算法向后处理算法21123458761110912st97324
18、227111118654356524BCOST(3,6)=minBCOST(2,2)+4,BCOST(2,3)+2=9BCOST(3,7)=minBCOST(2,2)+2,BCOST(2,3)+7,BCOST(2,5)+11=11BCOST(3,8)=minBCOST(2,2)+1,BCOST(2,4)+11,BCOST(2,5)+8=101632728V1V2V3V4V522123458761110912st973242271111186543565241632728BCOST(4,9)=minBCOST(3,6)+6,BCOST(3,7)+4=15BCOST(4,10)=minBCOST(
19、3,6)+5,BCOST(3,7)+3,BCOST(3,8)+5=14BCOST(4,11)=1691011V1V2V3V4V523123458761110912st97324227111118654356524163272891011BCOST(5,12)=minBCOST(4,9)+4,BCOST(4,10)+2,BCOST(4,11)+5=1612V1V2V3V4V524多段图的多段图的向后处理算法向后处理算法在计算每一个在计算每一个BCOST(i,j)的同时，记的同时，记下每个状态下每个状态(结点结点j)所做出的决策所做出的决策(即即,使使BCOST(i-1,j)+c(l,j)取最小值
20、的取最小值的 l 值值),设为设为D(i,j)，则可容易地求出这条最，则可容易地求出这条最小成本路径。小成本路径。25对于实例中的最小成本路径如下所示：对于实例中的最小成本路径如下所示：D(3,6)=3;D(3,7)=2;D(3,8)=2;D(4,9)=6;D(4,10)=6;D(4,11)=8;D(5,12)=10123458761110912st9732422711111865435652416327289101112V1V2V3V4V526多段图的多段图的向后处理算法向后处理算法Line procedure BGRAP(E,k,n,P)real BCOST(n),integer D(n-
21、1),P(k),r,j,k,nBCOST(1)0for j2 to n do 设设r是一个这样的结点，是一个这样的结点，E且使且使BCOST(r)+c(r,j)取小值取小值BCOST(j)BCOST(r)+c(r,j)D(j)rrepeatP(1)1;P(k)nfor jk-1 to 2 by-1 doP(j)D(P(j+1)repeatEnd BGRAPH计算出计算出BCOST(j)的值，并找出一的值，并找出一条最小成本路径条最小成本路径找出最小成本路径找出最小成本路径上的第上的第j个结点个结点274.3 每对结点之间的最短路径复习（略）284.4 最优二分检索树问题的描述问题的描述1）二分
22、检索树定义）二分检索树定义 二分检索树是一棵二元树，它或者为空，或者其每个二分检索树是一棵二元树，它或者为空，或者其每个结点含有一个可以比较大小的数据元素，且有：结点含有一个可以比较大小的数据元素，且有：的左子树的所有元素比根结点中的元素小；的左子树的所有元素比根结点中的元素小；的右子树的所有元素比根结点中的元素大；的右子树的所有元素比根结点中的元素大；的左子树和右子树也是二分检索树。的左子树和右子树也是二分检索树。注：注：二分检索树要求树中所有结点的元素值互异二分检索树要求树中所有结点的元素值互异29二分检索树ifforwhilerepeatloopifforrepeatloopwhile
23、对于一个给定的对于一个给定的标识符标识符集合，可能有集合，可能有若干棵若干棵不同的二分检索树不同的二分检索树:不同形态的二分检索树对标识符的不同形态的二分检索树对标识符的检索性能检索性能是是不同不同的。的。30二分检索树检索一棵二分检索树算法检索一棵二分检索树算法procedure SEARCH(T,X,i)i=Twhile i0 do case :XIDENT(i):i=RCHILD(i)endcaserepeatend REARCH31最优二分检索树问题最优二分检索树问题 设给定的标识符集合是设给定的标识符集合是a1,a2,an，并假定，并假定a1a2 an。设，设，P(i)是对是对ai检
24、索的概率，检索的概率，Q(i)是正被检索的标识符是正被检索的标识符X恰好满足：恰好满足：ai Xai+1，0in（设（设a0=-,an+1=+)时的概率，即一时的概率，即一种不成功检索情况下的概率。种不成功检索情况下的概率。则则 表示所有成功检索的概率表示所有成功检索的概率 表示所有不成功检索的概率表示所有不成功检索的概率 考虑所有可能的成功和不成功检索情况，共考虑所有可能的成功和不成功检索情况，共2n+1种可种可能的情况，有能的情况，有32二分检索树二分检索树（如右图所示）内结点：代表成功检索情况，刚好有n个。外结点：代表不成功检索情况，刚好有n1个。33二分检索树的预期成本二分检索树的预期
25、成本 预期成本预期成本：算法对于所有可能的成功检索情况和不成功检：算法对于所有可能的成功检索情况和不成功检索情况，平均所要做的比较次数。根据期望值计算方法，索情况，平均所要做的比较次数。根据期望值计算方法，平均检索成本平均检索成本每种情况出现的每种情况出现的概率概率该情况下所需的该情况下所需的比较比较次数次数 平均检索成本的平均检索成本的构成构成：成功检索成分成功检索成分不成功检索成分不成功检索成分 成功检索成功检索：在：在l级内结点终止的成功检索，需要做级内结点终止的成功检索，需要做l次比较次比较运算（基于二分检索树结构）。该级上的任意结点运算（基于二分检索树结构）。该级上的任意结点ai的的
26、成本检成本检索的成本分担额索的成本分担额为：为：P(i)*level(ai)；其中，其中，level(ai)=结点结点ai 的级数的级数=l34二分检索树的预期成本二分检索树的预期成本不成功检索：不成功检索的不成功检索的等价类等价类：每种不成功检索情况定义了一个：每种不成功检索情况定义了一个等价类，共有等价类，共有n+1个等价类个等价类Ei(0in)。其中，。其中，E0=X|Xa0 Ei=X|aiXai+1(1in)En=X|Xan 若若Ei处于处于l级，则算法需作级，则算法需作l-1次迭代。则，次迭代。则，l级上的外部结级上的外部结点的点的不成功检索的成本分担额不成功检索的成本分担额为：为：
27、Q(i)*(level(Ei)-1)则预期总的成本公式表示如下：则预期总的成本公式表示如下：35最优二分检索树最优二分检索树最优二分检索树问题最优二分检索树问题：求一棵使得求一棵使得预期成本预期成本最小最小的二分检索树的二分检索树例例4.9 标识符集合（标识符集合（a1,a2,a3）=（do,if,stop）。可）。可能的二分检索树如下所示。能的二分检索树如下所示。成成 功功 检检 索：索：3种种 不成功情况：不成功情况：4种种36最优二分检索树最优二分检索树stopdoifdoifstopstopifdoifdostopdostopif(a)(b)(c)(d)(e)37最优二分检索树最优二分
28、检索树1)等概率：等概率：P(i)=Q(i)=1/7 cost(a)=15/7 cost(b)=13/7 最优最优 cost(c)=15/7 cost(d)=15/7 cost(e)=15/7 2）不等概率：）不等概率：P(1)=0.5 P(2)=0.1 P(3)=0.05 Q(0)=0.15 Q(1)=0.1 Q(2)=0.05 Q(3)=0.05 cost(a)=2.65 cost(b)=1.9 cost(c)=1.5 最优最优 cost(d)=2.15 cost(e)=1.6ifdostopdostopif(b)(c)38多阶段决策过程多阶段决策过程 把构造二分检索树的过程看成一系列决策
29、的结果。把构造二分检索树的过程看成一系列决策的结果。决策的策略：决策树根，如果决策的策略：决策树根，如果a1,a2,an存在一棵二分存在一棵二分检索树，检索树，ak是该树的根，则内结点是该树的根，则内结点a1,a2,ak-1和外部结点和外部结点E0,E1,Ek-1将位于根将位于根ak的左子树中，而其余的结点将位于右的左子树中，而其余的结点将位于右子树中。子树中。ak由ak1,ak+2,an及Ek,Ek+1,En构成的二分检索树由a1,a2,ak-1及E0,E1,Ek-1构成的二分检索树39定义含义：含义：左、右子树左、右子树的的预期成本预期成本左、右子树的左、右子树的根根处处于于第一级第一级
30、左、右子树中所有结点的级数相对于子树的根左、右子树中所有结点的级数相对于子树的根测定，而相对于原树的根少测定，而相对于原树的根少140定义记：记：则，原二分检索树的预期成本可表示为：则，原二分检索树的预期成本可表示为：COST(T)=P(k)+COST(L)+COST(R)+W(0,k-1)+W(k,n)最优二分检索树最优二分检索树：COST(T)有最小值有最小值最优性原理成立最优性原理成立 若若T最优二分检索树，则最优二分检索树，则COST(L)和和COST(R)将分别是包含将分别是包含a1,a2,ak-1和和E0,E1,Ek-1、及、及ak1,ak+2,an和和Ek,Ek+1,En的最优二
31、分检索的最优二分检索(子子)树。树。记由记由ai+1,ai+2,aj和和Ei,Ei+!,Ej构成的二分检索树的成本为构成的二分检索树的成本为C(i,j)，则对，则对于最优二分检索树于最优二分检索树T有，有，COST(L)=C(0,k-1)COST(R)=C(k,n)41定义则，则，对任何对任何C(i,j)有，有，向前递推过程：向前递推过程：首先计算所有首先计算所有j-i=1的的C(i,j)然后依次计算然后依次计算j-i=2,3,n的的C(i,j)。C(0,n)=最优二分检索树的成本。最优二分检索树的成本。初始值初始值 C(i,i)=0 W(i,i)=Q(i)，0in42用动态归划求最优二分检索
32、树首先计算所有使得j-i=1的C(i,j)接着计算所有使得j-i=2的C(i,j).如果在这一计算期间，记下每棵Tij树的根R(i,j),那么最优二分检索树就可以由这些R(i,j)构造出来。43 用动态归划求最优二分检索树例例4.10 设设n=4,且且(a1,a2,a3,a4)=(do,if,read,while)。设设P(1:4)=(3,3,1,1)，Q(0:4)=(2,3,1,1,1)(概率值概率值“扩大扩大”了了16倍倍)初始：初始：W(i,i)=Q(i)C(i,i)=0 R(i,i)=0且有，且有，W(i,j)=P(j)+Q(j)+W(i,j-1)j-i=1阶段的计算：阶段的计算：W(
33、0,1)=P(1)+Q(1)+W(0,0)=8 C(0,1)=W(0,1)+minC(0,0)+C(1,1)=8 R(0,1)=1 W(1,2)=P(2)+Q(2)+W(1,1)=7 C(1,2)=W(1,2)+minC(1,1)+C(2,2)=7 R(1,2)=2 W(2,3)=P(3)+Q(3)+W(2,2)=3 C(2,3)=W(2,3)+minC(2,2)+C(3,3)=3 R(2,3)=3 W(3,4)=P(4)+Q(4)+W(3,3)=3 C(3,4)=W(3,4)+minC(3,3)+C(4,4)=3 R(3,4)=4例4.10(P135)44 用动态归划求最优二分检索树W,C,
34、R计算结果计算结果则，则，C(0,4)=32二分检索树：二分检索树：T04=2=T01(左子树），左子树），T24(右子树）右子树）T01=1=T00(左子树），左子树），T11(右子树）右子树）T24=3=T22(左子树），左子树），T34(右子树）右子树）0123402,0,03,0,01,0,01,0,01,0,018,8,17,7,23,3,33,3,4212,19,19,12,25,8,3316,25,211,19,2416,32,2W(j,j+i),C(j,j+i),R(j,j+i)ji45 用动态归划求最优二分检索树树的形态ifdoreadwhile46算法描述算法描述 proc
35、edure OBST(P,Q,n)/给定给定n个标识符个标识符a1a2an。已知成功检索的概率。已知成功检索的概率P(i),不成功检索概率不成功检索概率Q(i),0in。算法对于标识符。算法对于标识符ai+1,aj计算最优二分检索树计算最优二分检索树Tij的成本的成本C(i,j)、根、根 R(i,j)、权、权W(i,j)/real P(1:n),Q(0:n),C(0:n,0:n),W(0:n,0:n);integer R(0:n,0:n)for i0 to n-1 do (W(i,i),R(i,i),C(i,i)(Q(i),0,0)/置初值置初值/(W(i,i+1),R(i,i+1),C(i,
36、i+1)(Q(i)+Q(i+1)+P(i+1),i+1,Q(i)+Q(i+1)+P(i+1)repeat /含有一个结点的最优树含有一个结点的最优树/(W(n,n),R(n,n),C(n,n)(Q(n),0,0)for m2 to n do /找有找有m个结点的最优树个结点的最优树/for i0 to n-m do ji+m W(i,j)W(i,j-1)+P(j)+Q(j)k区间区间R(i,j-1),R(i+1,j)中使中使C(i,l-1)+C(l,j)取最小值的取最小值的l值值 /Knuth结论结论/C(i,j)W(i,j)+C(i,k-1)+C(k,j)R(i,j)k repeat rep
37、eat end OBST47计算时间计算时间 当当j-i=m时，有时，有n-m+1个个C(i,j)要计算要计算 C(i,j)的计算：的计算：(m)每个每个C(i,j)要求找出要求找出m个量中的最小值。个量中的最小值。则，则，n-m+1个个C(i,j)的计算时间：的计算时间：(nm-m2)对所有可能的对所有可能的m，总计算时间为总计算时间为：484.5 0/1背包问题背包问题问题描述问题描述背包问题中的背包问题中的xj限定只能取限定只能取0或或1值，用值，用KNAP(1,j,X)来表示这个问题来表示这个问题效益值效益值背包容量背包容量则则0/1背包问题就是背包问题就是KNAP(1,n,M)490
38、/10/1背包问题最优化原理证明背包问题最优化原理证明若若y1,y2,yn是最优解，则是最优解，则y2,y3,yn将是是将是是0/1 背包问题的子问题背包问题的子问题的最优解。因为，若的最优解。因为，若y2,y3 ,yn 是子是子问题的最优解，且使得问题的最优解，且使得500/10/1背包问题最优化原理证明背包问题最优化原理证明则y1,y2,y3 ,yn 将是原问题的可将是原问题的可行解，并且使得行解，并且使得这与假设这与假设y1,y2,yn是最优解相矛盾。是最优解相矛盾。因此，因此，0/1 背包问题具有最优子结构性质得背包问题具有最优子结构性质得以证明，可以用动态规划的方法求最优解。以证明，
39、可以用动态规划的方法求最优解。510/1背包问题背包问题-解决方法解决方法根据问题描述，可通过作出变量根据问题描述，可通过作出变量x1,x2,xn的一的一个决策序列来得到它的解。个决策序列来得到它的解。假定决策假定决策x的次序为的次序为x1,x2,xn则在对则在对x1作出决策后，问题处于下列两种状态：作出决策后，问题处于下列两种状态：X1=0,背包的剩余容量为背包的剩余容量为M，没有产生任何效益，没有产生任何效益X1=1,背包剩余容量为背包剩余容量为M-w1，效益值增加了，效益值增加了p1显然，剩下来对显然，剩下来对x2,xn的决策相对于决策了的决策相对于决策了x1后所产生的问题状态应该是最优
40、的，否则，后所产生的问题状态应该是最优的，否则，x1,x2,xn就不可能是最优的决策序列。就不可能是最优的决策序列。520/1背包问题背包问题解解决方法决方法设设fj(X)是是KNAP(1,j,X)最优解的值最优解的值则则fn(M)(KNAP(1,n,M)可表示为：可表示为：fn(M)=max fn-1(M),fn-1(M-wn)+pn 则对于任意的则对于任意的fi(X)(KNAP(1,i,X)可表示可表示公式公式4.14为：为：fi(X)=max fi-1(X),fi-1(X-wi)+pi 为了能为了能由前向后递推由前向后递推而最后求解出而最后求解出fn(M),须从须从f0(X)开始开始对于
41、所有的对于所有的X0，有，有f0(X)=0；当；当X0时，有时，有f0(X)=-根据递推关系式，马上可求出根据递推关系式，马上可求出0Xw1和和Xww1 1情况下的情况下的f f1 1(X)(X)的值的值530/1背包问题实例背包问题实例例：例：n=3,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5),M=6。利用公式利用公式4.14递推求解如下：递推求解如下：当当X0时时,f0(X)=-;当当X 0时时,有有f0(X)=0当当X0时时,f1(X)=-当当0X2时时,f1(X)=maxf0(X),f0(X-2)+1=max0,-+1+1=0当当X2时时,f1(X)=m
42、axf0(X),f0(X-2)+1=max0,0+1=1540/1背包问题实例背包问题实例当当X0 时时,f2(X)=-当当0X2时时,f2(X)=maxf1(X),f1(X-3)+2=max 0,-+2+2 =0当当2X3 时时,f2(X)=maxf1(X),f1(X-3)+2=max 1,-+2+2 =1当当3X5 时时,f2(X)=maxf1(X),f1(X-3)+2=max 1,0+2=2当当 5X 时时,f2(X)=maxf1(X),f1(X-3)+2=max 1,1+2=3例：例：n=3,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5),M=6。550/1
43、背包问题实例背包问题实例当当X0 时时,f3(X)=-当当0X2 时时,f3(X)=maxf2(X),f2(X-4)+5=max0,-+5=0当当2X3 时时,f3(X)=maxf2(X),f2(X-4)+5=max1,-+5=1当当3X4 时时,f3(X)=maxf2(X),f2(X-4)+5=max2,-+5 =2当当4X5 时时,f3(X)=maxf2(X),f2(X-4)+5=max2,0+5 =5当当5X6 时时,f3(X)=maxf2(X),f2(X-4)+5=max3,0+5 =5当当6X7 时时,f3(X)=maxf2(X),f2(X-4)+5=max3,1+5 =6当当7X9
44、 时时,f3(X)=maxf2(X),f2(X-4)+5=max3,2+5 =7当当9X 时时,f3(X)=maxf2(X),f2(X-4)+5=max3,3+5 =8例：例：n=3,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5),M=6。560/1背包问题实例背包问题实例570/1背包问题算法背包问题算法procedure DynamicKnapsack(p,w,n,M,f)/二维数组二维数组f(1:n,1:M)的定义与的定义与fj(X)相同相同for i 0 to M do f(0,i)0;repeatfor i 0 to n do f(i,0)0;repeat
45、for i 1 to n do for j 1 to M do if w(i)j then f(i,j)=maxf(i-1,j-w(i)+p(i),f(i-1,j);else f(i,j)=f(i-1,j)end if repeat repeat 输出输出f(n,M);end DynamicKnapsack580/1背包问题实例背包问题实例可通过检测可通过检测fi的取值情况可以确定获得最优解的最的取值情况可以确定获得最优解的最优决策序列优决策序列f3(M)=6是在是在X3=1的情况下取得的，因此的情况下取得的，因此X3=1f3(M)-p3=1，f2(X)和和f1(X)都可取都可取1，则，则x2
46、=0f0不能取值不能取值1，故，故x1=1于是最优决策序列为于是最优决策序列为(x1,x2,x3)=(1,0,1)也可通过图解法得到也可通过图解法得到fi-1(X-wi)+pi的图像的图像可由可由fi-1(X)在在x轴上右移轴上右移wi个单位，然个单位，然后上移后上移pi个单位得到个单位得到fi(X)的图像的图像由由fi-1(X)和和fi-1(X-wi)+pi 的函数曲线按的函数曲线按X相同时相同时取最大值的规则归并而成取最大值的规则归并而成590/1背包问题实例背包问题实例图图解法解法fi-1(X-wi)+pifi(X)i=0:函数不存在函数不存在f0(X)i=1:f0(X-2)+1f1(X
47、)当当X0时时,f0(X)=-;当当X 0时时,有有f0(X)=0当当X0时时,f1(X)=-当当0X2时时,f1(X)=maxf0(X),f0(X-2)+1=max0,-+1+1=0当当X2时时,f1(X)=maxf0(X),f0(X-2)+1=max0,0+1=160i=2:f1(X-3)+2f2(X)f1(X)当当X0 时时,f2(X)=-当当0X2时时,f2(X)=maxf1(X),f1(X-3)+2=max 0,-+2+2 =0当当2X3 时时,f2(X)=maxf1(X),f1(X-3)+2=max 1,-+2+2 =1当当3X5 时时,f2(X)=maxf1(X),f1(X-3)
48、+2=max 1,0+2=2当当 5X 时时,f2(X)=maxf1(X),f1(X-3)+2=max 1,1+2=361i=3:f2(x-4)+5f3(X)当当X0 时时,f3(X)=-当当0X2 时时,f3(X)=maxf2(X),f2(X-4)+5=max0,-+5=0当当2X3 时时,f3(X)=maxf2(X),f2(X-4)+5=max1,-+5=1当当3X4 时时,f3(X)=maxf2(X),f2(X-4)+5=max2,-+5 =2当当4X5 时时,f3(X)=maxf2(X),f2(X-4)+5=max2,0+5 =5当当5X6 时时,f3(X)=maxf2(X),f2(X
49、-4)+5=max3,0+5 =5当当6X7 时时,f3(X)=maxf2(X),f2(X-4)+5=max3,1+5 =6当当7X9 时时,f3(X)=maxf2(X),f2(X-4)+5=max3,2+5 =7当当9X 时时,f3(X)=maxf2(X),f2(X-4)+5=max3,3+5 =8620/1背包问题实例背包问题实例图图解法解法由图可看出以下几点：由图可看出以下几点：每一个每一个fi 完全由一些序偶完全由一些序偶(Pj,Wj)组成的集合所说明，其组成的集合所说明，其中中Wj是使是使fi 在其处产生一次阶跃的在其处产生一次阶跃的X值，值，Pj=fi(Wi)。第一对序偶第一对序偶
50、(P0,W0)=(0,0)如果有如果有r次阶跃，就还要知道次阶跃，就还要知道r对序偶对序偶(Pj,Wj),1jrjrr对序偶中，假定对序偶中，假定WjWj+1，由公式，由公式4.14可得可得PjM的那的那些序偶些序偶(Pj,Wj)除掉。除掉。67最优解序列的确定最优解序列的确定这样生成的这样生成的Si的所有序偶是背包问题的所有序偶是背包问题KNAP(1,i,X)在在0XM各种情况下的最优解。各种情况下的最优解。KNAP(1,n,M)的最优解的最优解fn(M)由由Sn的最后一对序偶的最后一对序偶的的P值给出。值给出。如果已找到如果已找到 Sn 的最末序偶的最末序偶(Pl,Wl),那么，使那么，使