计算机算法设计与分析：6第六章动态规划

1、1第六章动态规划2目录6.1 一般方法6.2 多段图6.3 每对节点之间的最短路径(略)6.4 最优二分检索树6.5 0/1背包问题6.6 可靠性设计6.7 货郎担问题6.8 流水线调度问题36.1 一般方法动态规划适用的问题动态规划的求解思想最优性原理多段图问题的最优性原理0/1背包问题的最优性原理最优化决策序列的表示多段图的递推分析0/1背包问题的递推分析4动态规划适用的问题有这样一类问题，它们的活动过程可分为若干个阶段，在任一阶段i之后的行为都依赖于i 阶段的过程状态，而与i 阶段之前的过程无关，这样就构成了一个多阶段决策过程。在多阶段决策过程的每一个阶段，都有多种决策可供选择，但必须从

2、中选取一种。一旦各种阶段的决策选定之后，就构成了一个决策序列。决策序列不同会导致问题结果也不同。获取最优解？5动态规划的求解思想动态规划的目标是在所有允许选择的决策序列中选取一个会获得问题最优解的决策序列，即最优决策序列。动态规划的求解思想可以归纳为两个步骤：证明问题满足最优性原理给出递推关系式20世纪50年代，贝尔曼等人根据这类问题多阶段决策的特性，提出了解决这类问题的“最优性原理”，从而创建了一种新的算法设计方法 动态规划。贝尔曼认为，利用最优性原理以及所获得的递推关系式去求解最优决策序列可以使枚举量急剧下降。6最优性原理最优性原理(Principle of Optimality) 过程的

3、最优决策序列具有如下性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。如果所求解的问题满足最优性原理，则说明用动态规划方法有可能解决该问题；而解决该问题的关键在于求解递推关系式。7多段图问题(multistage graph problem)多段图G(V, E)是一个有向图。它具有如下特性：图中的结点被划分成 k 2个不相交的集合Vi ，1ik，其中V1和Vk分别只有一个结点 s (源点) 和 t (汇点)。图中所有的边均具有如下性质： 若uVi，则vVi1，1ik，且每条边均 附有成本c(u, v)。从s到t的一条路径成本是这条路径上边

4、的成本和。多段图问题是求由s到t的最小成本路径。8例：多段图问题(multistage graph problem)2345876111091s12t97324227111118654356524V1V2V3V4V59多段图问题的最优性原理证明假设s,v2,v3,vk1,t是一条由s到t的最短路径。再假设从源点s开始，已作出了到结点v2的决策，因此v2就是初始决策所产生的状态。如果把v2看成是原问题的一个子问题的初始状态，解决这个子问题就是找出一条由v2到t的最短路径。这条最短路径显然是v2,v3,vk1,t。如果不是，设v2,q3,qk1,t由v2到t的更短路径，则这条路径肯定比v2,v3,

5、vk1,t路径短，这与假设矛盾，因此最优性原理成立。证明满足最优性原理: 设最优决策序列的形式 确定初始状态和初始决策 初始决策所产生的状态 其余决策相对于100/1背包问题背包问题中的xj限定只能取0或1值，用KNAP(l, j, X)来表示这个问题。 极大化: pixi约束条件: wi xi X xi0或1，lijlijlij若对于有n个物品，容量为M的背包，则0/1背包问题就可表示为KNAP(1, n, M)。11最优性原理对于0/1背包问题成立设y1,y2,yn分别为x1,x2,xn的0/1值的最优序列。若y10，则y2,y3,yn必须相对于KNAP(2,n,M)问题构成一个最优序列。

6、如若不然，则y1,y2,yn就不是KNAP(1,n,M)的最优序列。若y11，则y2,y3,yn必须是KNAP(2,n,Mw1)的最优序列。如若不然，则必有另一个0/1序列z2,z3,zn使得wizi Mw1(2in)且pizi piyi(2in)。因此，序列y1,z2, z3,zn是一个对问题KNAP(1,n,M)具有更大效益值的序列。这与假设相矛盾，所以0/1背包问题的最优性原理成立。12设S0是问题的初始状态，假定要作n次决策xi，1in X1r1, 1, r1, 2, , r1, p1是x1的可能决策值的集合，而 S1, j1是在选取决策值r1, j1以后所产生的状态，1j1p11j1

7、p1又设1, j1是相应于状态S1, j1的最优决策序列； 则相应于S0的最优决策序列就是r1, j11, j1 | 1j1p1中最优的序列，记为OPT r1, j11, j1 = r11 最优决策序列的表示13如果已作了k1次决策，1k1n，设x1, xk1的最优决策值是r1,rk1，它们所产生的状态为S1,Sk1又设Xkrk, 1, rk, 2, , rk, pk是xk的可能值的集合, Sk, jk是选取rk, jk决策之后所产生的状态，1jkpkk, jk 是相应于Sk, jk的最优决策序列 因此相应于Sk1的最优决策序列是：1jkpkOPT rk, jkk, jk rkk 于是相应于S

8、0的最优决策序列为：r1,rk1, rk ,k14多段图的递推分析向前处理法(forward approach)从最后阶段开始，以逐步向前递推的方式，列出求解前一阶段决策值的递推关系式，即根据xi1, , xn的那些最优决策序列来列出求取xi决策值的关系式。向后处理法(backward approach) 从初始阶段开始，以逐步向后递推的方式，列出求解后一阶段决策值的递推关系式，即根据x1, , xi1的那些最优决策序列来列出求取xi决策值的关系式。150/1背包问题的递推分析向前处理法 设gj(x)是KNAP(j1,n,x)最优解的值，显然g0(M)是KANP(1,n,M)最优解的值。由于x

9、i可能的取值是0或1，因此可得： g0(M)maxg1(M), g1(Mw1)p1 gj(x)maxgj1(x), gj1(xwj1)pj1向后处理法 设fi(x)是KNAP(1,i,x)最优解的值 fi(x)maxfi1(x), fi1(xwi)pi166.2 多段图多段图向前处理递推关系式向前处理的计算过程向前处理算法及执行过程多段图向后处理递推关系式向后处理的计算过程向后处理算法多段图的应用17设P(i, j)是一条从Vi中的节点j 到汇点t 的最小成本路径，COST(i, j)表示这条路径的成本。根据向前处理方法： COST(i, j) min c(j, l)COST(i1, l) 其

10、中：lVi1，E, c(j, l)表示该边的成本。V2Vk-1V3tsVi多段图向前处理递推关系式向前处理法：从最后阶段开始，逐步向前递推，根据xi1, , xn的那些最优决策序列来列出求取xi决策值的关系式。18初始化：对于k段图，当ik1时， 如果E，有COST(k1, j) c(j, t)， 如果E，有COST(k1, j)1s9732V123454227111118V2876654356V31110912t524V4V5多段图向前处理的计算过程19多段图向前处理的计算过程COST(4, 9)c(9,12)4COST(4,10)c(10,12)2COST(4,11)c(11,12)511

11、10912t524V4V5876654356V3COST(3,6)minc(6,9)COST(4,9) , c(6,10)COST(4,10) min64, 527COST(3,7)minc(7,9)COST(4,9) , c(7,10)COST(4,10) min44, 325COST(3,8)minc(8,10)COST(4,10) , c(8,11)COST(4,11) min52, 657COST(i, j)min c(j, l)COST(i1, l) 201s9732V123454227111118V21110912t524V4V5876654356V3COST(2,2)minc(2

12、,6)COST(3,6), c(2,7)COST(3,7), c(2,8)COST(3,8)min47, 25, 177COST(3,6)7COST(3,7)5COST(3,8)7COST(2,3)min27,759COST(2,4)min11718COST(2,5)min115,8715COST(1,1)minc(1,2)COST(2,2), c(1,3)COST(2,3), c(1,4)COST(2,4), c(1,5)COST(2,5)min97,79,318,215=1621在计算每个COST(i, j)的同时，记下每个状态（结点j）所做出的决策（即l 的取值）,令D(i, j)l，则

13、容易求出这条最小成本的路径。COST(2,2)minc(2,6)COST(3,6), c(2,7)COST(3,7), c(2,8)COST(3,8)7COST(1,1)minc(1,2)COST(2,2), c(1,3)COST(2,3), c(1,4)COST(2,4), c(1,5)COST(2,5)16D(1, 1)2D(2, 2)7D(2, 3)6D(2, 4)8D(2, 5)8D(3, 6)10D(3, 7)10D(3, 8)10COST(3,7)minc(7,9)COST(4,9) , c(7,10)COST(4,10)51271012最小成本的路径为：22多段图的向前处理算法p

14、rocedure FGRAPH(E,k,n,P)real COST(n); integer D(n1), P(k), r, j, k, n;COST(n)0;for jn1 to 1 by 1 do 寻找结点r, 满足E且使c(j,r)COST(r)值最小 COST(j) c(j,r)COST(r); D(j)r;repeatP(1)1; P(k)n;for j2 to k1 do P(j)D(P(j1) ;end FGRAPH通过计算找到一条最小成本的路径编程实现算法时要先将多段图用邻接表表示为了算法描述的简单，对结点进行编号，从V1开始 s 编为1号，然后V2中的结点依次编为2,3,4,5

15、号，按此规则编下去，有了编号可以将COST, D中表示段数的第一个下标i省略掉。 数组P用来保存最小成本路径上结点231s9732234542271111181110912t524876654356邻接表：邻接表是图的一种链式存储结构，对图中的每个顶点建立一个单链表，链表中的结点有3个域，分别存储顶点, 边的成本和下一个结点的指针。12345678910111211841221251292733425462718267711788695104931051061124k5; n12;COST(12)0;for j11 downto 1 do COST(j)minc(j,r)COST(r); D(

16、j)r ; P(1)1; P(k)12;for j2 to 4 do P(j)D(P(j1) ;1234567891011120123456789101112345112COSTDPCOST(11)5COST(10)2COST(9)4512241212COST(8)7COST(7)5COST(6)7D(8)10D(7)10D(6)10710571010COST(5)15COST(4)18COST(3)9COST(2)7 D(11)12 D(10)12 D(9)12D(5)8D(4)8D(3)6D(2)71581897867D(1)2COST(1)161622710算法6.1的执行过程25算法6

17、.1 时间复杂度和空间复杂度(ne)n是图G中节点个数。e是图G中边的个数。(k)k是最小成本路径节点个数。计算时间：总计在(ne)以内。所需空间：除输入参数外，还需要COST、D、P。多段图的向前处理算法procedure FGRAPH(E,k,n,P)real COST(n); integer D(n1), P(k), r, j, k, n;COST(n)0;for jn1 to 1 by 1 do 寻找结点r, 满足E且使c(j,r)COST(r)值最小 COST(j) c(j,r)COST(r); D(j)r;repeatP(1)1; P(k)n;for j2 to k1 do P(j

18、)D(P(j1) ;end FGRAPH26多段图向后处理递推关系式设BP(i, j)是一条从源点s到 Vi中的结点j的最小成本路径，BCOST(i, j)表示这条路径的成本，根据向后处理方法： BCOST(i, j)minBCOST(i1, l)c(l, j) 其中： lVi1，E，c(l, j)表示该边的成本。初始化：对于k段图，当i2时, 如果E，有COST(2, j)c(s, j)如果E，有COST(2, j)向后处理法：从初始阶段开始，逐步向后递推，根据x1, , xi1的那些最优决策序列来列出求取xi决策值的关系式。27多段图向后处理的算法 对于k段图，当i2时，有BCOST(2,

19、 j)c(1, j)，所以可以通过上述公式，对所有jV3，计算BCOST(3, j)，依次向后求解，最后计算出BCOST(k, t)；同样的，在计算每个BCOST(i, j)的同时，记下每个状态所做出的决策(即l 的取值)，令D(i, j)l 由于我们已经按规则对结点进行了编号，所以这里可以省略BCOST和D中的第一个下标。设BP(i, j)是一条从源点s到 Vi中的结点j的最小成本路径，BCOST(i, j)表示这条路径的成本，根据向后处理方法有公式6.6 ： BCOST(i, j) minBCOST(i1, l ) c(l, j )其中：lVi1 , 边E, c(l, j)表示该边的成本2

20、8多段图向后处理算法的计算过程1s973223454227111118876BCOST(2)c(1,2)9BCOST(3)c(1,3)7BCOST(4)c(1,4)3BCOST(5)c(1,5)2BCOST(6)minBCOST(2)c(2,6), BCOST(3)c(3,6) min94,729BCOST(7)11 BCOST(8)10D(2)1D(3)1D(4)1D(5)1D(6)3D(7)2D(8)2D(9)6D(10)6D(11)8BCOST(9)15 BCOST(10)14BCOST(11)16BCOST(12)16 D(12)101361012最小成本的路径为：BCOST(j)mi

21、nBCOST(l)c(l, j) 29procedure BGRAPH(E,k,n,P)real BCOST(n); int D(n1), P(k), r, j, k, n;BCOST(1)0;for j2 to n do 寻找结点r, 满足E且使BCOST(r)c(r, j)值最小 BCOST(j) BCOST(r)c(r, j); D(j)r ;repeatP(1)1; P(k)n;for jk1 downto 2 do P(j)D(P(j1) ;end BGRAPH算法6.2 多段图的向后处理算法301s9732234542271111181110912t524876654356对于向后

22、处理算法多段图用逆邻接表来存储1234567891011129171312122731154223121141154921051166475637586831多段图的应用考虑把n个资源分配给r个项目的问题。N(i, j)：表示把j个资源分配给项目i所获得的净利，0jn，1ir。要求使得总净利达到最大值。这个问题可以用多段( r1段)图来表示。第1段和第r1段分别只包含一个结点，第2段至第r段分别包含n1个结点。 V(i, j)表示把j个资源分配给前i1个项目， 2ir 。表示项目i分配到lj个资源，则获取到N(i, lj)的净利。从V(1,0)到V(i1,l)的路径表示前i个项目一共分配到l个

23、资源。当jn且ir时，边具有形式，成本值为maxN(r, p)。0pnj326.4 最优二分检索树二分检索树检索二分检索树的算法6.4问题描述与递推关系式分析一个实例计算时间复杂度递推关系式的改进算法6.533二分检索树二分检索树：T是一个二叉树，它或者为空，或者其每个结点含有一个可比较大小的数据元素，并且：T的左子树的所有元素比根结点T中的元素小T的右子树的所有元素比根结点T中的元素大T的左、右子树也是二分检索树注意：二分检索树中的所有结点的元素是互异的。ifforwhilerepeatloop34算法6.4 检索二分检索树算法思想：为确定X是否在二分检索树中出现，先将X与根比较：若X比根中

24、的元素小则检索左子树若X等于根中的元素则检索成功终止若X比根中的元素大则检索右子树 procedure SEARCH(T, X, i)i T;while i0 do if XIDENT(i) then iLCHILD(i) endif if XIDENT(i) then return endif if XIDENT(i) then iRCHILD(i) endifrepeatend SEARCH每个结点有3个信息段，LCHILD，RCHILD，IDENT。若X不在T中，则i0；否则，将i置成使得IDENT(i)X。35问题描述与分析已知一个固定的标识符集合，希望产生一种构造二分检索树的方法，使

25、平均检索次数最小。可以预料，同一个标识符集合的不同二分检索树有不同的性能特征。一个例子标识符集(a1,a2,a3,a4,a5)(for,if,loop,repeat,while)ifforwhilelooprepeat图aa1a2a3a4a5图bifforwhilelooprepeata1a2a3a4a5最坏情况下，图a需要进行4次比较，而图b只需要3次比较。假设每个节点成功检索的概率是1/5，则在平均成功情况下，图a需要12/5次比较，图b需要11/5次比较。36一般情况下，要检索的那些标识符具有不同的概率，而且存在不成功检索的情况。用圆结点(内结点)表示给出的n个标识符，对应n种成功的情况

26、。方结点(外结点)表示不成功检索的情况，有n1个外结点。a2a1a5a3a4E0E1E2E3E4E5 设给定的标识符集是(a1, a2, , an)，a1 a2 an P(i)是对Xai成功检索的概率 Q(i)是aiXai1不成功检索的概率（假定a0，an1 ） 则有P(i) Q(i) 11in0in37二分检索树的预期成本为：P(i)level(ai)Q(i)(level(Ei)1)1in0in一次成功检索在一个内结点(l 级)处终止，算法中的循环要执行l 次，所以内结点ai的预期成本为P(i)level(ai)一次不成功检索在一个外结点处(l 级)终止，算法中循环要执行l1次，所以外结点E

27、i的预期成本为Q(i)(level(Ei)1)a2a1a5a3a4E0E1E2E3E4E5定义：标识符集(a1, a2, , an)的最优二分检索树是一棵使P(i)level(ai)Q(i)(level(Ei)1)取最小值的树。38例：标识符集(a1, a2, a3)(do, if, stop)，有5种可能的二分检索树：图adoa1ifa2stopa3E3E1E2E0doa1stopa3图bE3E0E1E2ifa2图ddoa1stopa3E3E0E1E2ifa2图cdoa1ifa2E3E0E1E2stopa3图edoa1stopa3E3E0E1E2ifa239图adoa1ifa2stopa3E

28、3E1E2E01.设内外结点概率相同P(i)Q(i)172.设内外结点概率不同P(i)(0.5, 0.1, 0.05)，Q(i)(0.15,0.1,0.05,0.05)cost(a)=P(1)3P(2)2P(3)1 +Q(0)3Q(1)3Q(2)2Q(3)11) cost(a) =31721717 31731721717 =1572) cost(a) =30.520.10.05 30.1530.120.050.05 =2.6540doa1stopa3图bE3E0E1E2ifa2图ddoa1stopa3E3E0E1E2ifa2图cdoa1ifa2E3E0E1E2stopa3图edoa1stopa

29、3E3E0E1E2ifa2cost(b-1)137cost(b-2)1.9cost(c-1)=157cost(c-2)1.5cost(d-1)157cost(d-2)2.15cost(e-1)157cost(e-2)1.6cost(a-1)157cost(a-2)2.65对于第1种情况，内、外结点概率相同, 图b所示的树最优。对于第2种情况，内、外结点概率不同, 图c所示的树最优。41递推关系式分析为了把动态规划方法应用于得到一棵最优二分检索树的问题，需要把构造这样的一棵树看成是一系列决策的结果，而且要列出求取最优决策序列的递推式。对于ai，1in，决策出哪一个作为T的根结点。如果选择ak作为

30、根结点，那么内结点a1, a2, , ak1和外结点E0, E1, , Ek1都将位于这个根的左子树上，而内结点ak1, , an和外结点Ek, , En将位于这个根的右子树上。a1, a2, , ak1, ak, ak1, , anE0, E1, E2,Ek1, Ek, Ek1,EnTT的左子树LT的右子树R42递推关系式分析1ik 定义左子树的成本：COST(L)P(i)level(ai) Q(i)(level(Ei) 1)0ikkin 定义右子树的成本：COST(R)P(i)level(ai) Q(i)(level(Ei) 1)kin不是在T中的级别，而是在各自子树中的级别。COST(T

31、)P(i)level(ai)Q(i)(level(Ei) 1)1in0in COST(L) COST(R) P(k) P(i) Q(i) P(i) Q(i)用W(i, j)表示，W(i, j)Q(i)(Q(l)P(l)li1j W(i, j)W(i, j1)Q(j)P(j)W(k, n)W(0, k1) 1ik 0ikkin kin43doa1ifa2stopa3E3E0E1E2图b例：选a2为根结点，k2，设P(i)Q(i)17COST(L)P(1)1+Q(0)1+Q(1)1117+117+11737COST(R)P(3)1+Q(2)1+Q(3)1117+117+11737W(0, k1)W

32、(0,1)Q(0)Q(1)P(1)17171737W(k, n)W(2,3)Q(2)Q(3)P(3)171717=37COST(T)P(2)COST(L)COST(R)W(0,1)W(2,3) 1737373737137COST(T)P(k)COST(L)COST(R)W(0, k1)W(k, n)44根据最优性原理：如果T是最优的，那么COST(T)必定是最小值。COST(L)和COST(R)也必定是最小值。用C(i, j)表示包含ai1, aj和Ei ,Ej的最优二分检索树的成本。树T的预期成本：COST(T)P(k)COST(L)COST(R)W(0, k1)W(k, n)COST(T)

33、C(0, n)COST(L)C(0, k1)COST(R)C(k, n)C(0,n)minC(0, k1)C(k, n)P(k)W(0, k1)W(k, n)1knk不同，C(0, k1)C(k, n)的值也会不同。选择k，使得该式的取值最小。 将上式一般化，对于任何c(i, j)有下式：C(i, j)minC(i, k1)C(k, j)P(k)W(i, k1)W(k, j)ikjminC(i, k1)C(k, j)W(i, j)ikjP(k)Q(i)Q(i1)P(i1)Q(k1)P(k1) Q(k)Q(k1)P(k1)Q(j)P(j)W(i,j)45C(i, j)minC(i, k1)C(k

34、, j)W(i, j)ikj考虑公式初始值： C(i, i)0 W(i, i)Q(i)，0in然后，基于公式计算使ji1的C(i, j)，ji2 的C(i, j)， ji3的C(i, j)等等。在计算期间记下每棵树Tij的根R(i, j)，那么最优二分检索树就由这些R(i, j)构造出来。( R(i, j)是使C(i, j)取最小值的k值 )内结点个数为0一个实例：n4，(a1, a2,a3, a4)(do, if, read, while) P(1:4)(3,3,1,1)；Q(0:4)(2,3,1,1,1) (为计算方便P、Q的值都乘以16)(1) ji1时, 0i4a1E0E1a2E1E2

35、a3E2E3a4E3E4C(0,1)C(1,2)C(2,3)C(3,4)46W(0,1)Q(0)Q(1)P(1)2338R(0,1)k1k10k1C(0,1)minC(0,0)C(1,1)W(0,1)088C(0,1)W(1,2)Q(1)Q(2)P(2)3137k21k2C(1,2)minC(1,1)C(2,2)W(1,2)077R(1,2)k2W(2,3)3C(2,3)3R(2,3)k3W(3,4)3C(3,4)3R(3,4)k4C(1,2)C(2,3)C(3,4)a1E0E1a2E1E2a3E2E3a4E3E4P(1:4)(3,3,1,1)；Q(0:4)(2,3,1,1,1)47P(1:4

36、)(3,3,1,1); Q(0:4)(2,3,1,1,1)(2) ji2时，0i3C(0,2)C(1,3)C(2,4)min07, 8012=190k2C(0,2) min C(0,0)C(1,2), C(0,1)C(2,2)W(0,2)k1k2R(0,2)k1W(1,3)W(1,2)Q(3)P(3)3131191k3C(1,3) min C(1,1)C(2,3), C(1,2)C(3,3)W(1,3)k2k3min03,70912R(1,3)k2W(0,2)W(0,1)Q(2) P(2) 8 1 3 12W(0,1)8C(0,1)8R(0,1)1W(1,2)7C(1,2)7R(1,2)2W(

37、2,3)3C(2,3)3R(2,3)3W(3,4)3C(3,4)3R(3,4)4W(2,4)5 C(2,4)8 R(2,4)k3a2E1E2a1E0a3E2E3a2E1a4E3E4a3E248W(0,3)W(0,2)Q(3) P(3) 121114min012,83,19014111425R(0,3)k2W(1,4)11 C(1,4)19 R(1,4)k20k3C(0,3)minC(0,0)C(1,3), C(0,1)C(2,3),C(0,2)C(3,3)W(0,3)k1k2k3P(1:4)(3,3,1,1); Q(0:4)(2,3,1,1,1)W(0,2)12C(0,2)19R(0,2)1W

38、(1,3)9C(1,3)12R(1,3)2W(2,4)5 C(2,4)8R(2,4)3C(0,3)C(1,4)a3E2E3a2a1E0E1a2E1a4E3E4a3E2(3) ji3时，0i2W(0,1)8C(0,1)8R(0,1)1W(1,2)7C(1,2)7R(1,2)2W(2,3)3C(2,3)3R(2,3)3W(3,4)3C(3,4)3R(3,4)449W(0,4)W(0,3)Q(4)P(4)16 min019,88,193,25016161632R(0,4)k2C(0,4)minC(0,0)C(1,4),C(0,1)C(2,4),C(0,2)C(3,4),C(0,3)C(4,4)W(0

39、,4)k1k2k3k40k4P(1:4)(3,3,1,1); Q(0:4)(2,3,1,1,1)W(0,3)14C(0,3)25R(0,3)2W(1,4)11C(1,4)19R(1,4)2a2a1E0E1a4E3E4a3E2ifdowhileread(4) ji4时，0i1W(0,2)12C(0,2)19R(0,2)1W(1,3)9C(1,3)12R(1,3)2W(2,4)5 C(2,4)8R(2,4)3W(0,1)8C(0,1)8R(0,1)1W(1,2)7C(1,2)7R(1,2)2W(2,3)3C(2,3)3R(2,3)3W(3,4)3C(3,4)3R(3,4)450W(0,0)2C(0

40、,0)0R(0,0)0W(1,1)3C(1,1)0R(1,1)0W(2,2)1C(2,2)0R(2,2)0W(3,31C(3,3)0R(3,3)0W(4,4)1C(4,4)0R(4,4)0初始：ji0W(0,4)16C(0,3)32R(0,3)2ji0123402,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(0,1)8C(0,1)8R(0,1)1W(1,2)7C(1,2)7R(1,2)2W(2,3)3C(2,3)3R(2,3)3W(3,4)3C(3,4)3R(3,

41、4)4W(0,2)12C(0,2)19R(0,2)1W(1,3)9C(1,3)12R(1,3)2W(2,4)5 C(2,4)8R(2,4)3W(0,3)14C(0,3)25R(0,3)2W(1,4)11C(1,4)19R(1,4)2初始：ji1初始：ji2初始：ji3初始：ji451时间复杂度分析按(ji)1,2,n的顺序去计算C(i, j)。当jim时，有nm1个C(i, j)要计算。每个C(i, j)的计算要求找出m个量中的最小值，因此一个这样的C(i, j)能够在(m)时间内计算出来。对于具有jim的所有C(i, j)总的计算时间是(nmm2)。对于所有的jim，m1,2,n，有：(nm

42、m2) (n3)1mnC(i, j)minC(i, k1)C(k, j)W(i, j)ikj52算法6.5 找最小成本二分检索树P136。D.E.Knuth的优化方法求最优的k可以通过把检索限制在区间R(i,j1)kR(i1,j)求解递归关系式。这种情况下，计算时间为(n2)。C(i, j)minC(i, k1)C(k, j)W(i, j)R(i,j1)kR(i1,j)初始值：W(i,i)Q(i)；W(i,i1)Q(i)P(i1)Q(i1); R(i,i)0； R(i,i1)i1; C(i,i)0； C(i,i1)Q(i)P(i1)Q(i1);536.5 0/1背包问题问题描述递推关系式分析向

43、后处理法函数描述图解方法求解问题序偶对方法求解问题算法6.6非形式化的背包算法DKP形式化的背包算法DKNAPDKNAP分析与改进54问题描述 0/1背包问题的形式描述KNAP(1, n, M)极大化 pi xi xi0或1, pi0约束条件 wi xi M wi0, 1in1in 0/1背包问题要求物品或者整件装入背包中，或者根本不装入(即不能装入物品的一部分)，所以xi限定只能取0或1值，可以用KNAP(1, n, M)表示这个问题。1in55最优性原理证明：假设决策x的次序为x1, x2, xn，则在对x1作出决策后，问题处于下列两种状态：x10, 背包剩余容量为M，没有产生任何效益；x

44、11，背包剩余容量为Mw1，效益值增加了p1。显然对x2, xn的决策相对于决策了x1后所产生的问题状态应该是最优的，否则 x1, x2, xn就不可能是最优的决策序列。设fi(X)是KNAP(1,i,X)最优解的值，那么fn(M)可表示为：fn(M)max fn1(M), fn1(Mwn)pn 对于任意的fi(X)，i0 有以下公式： fi(X)max fi1(X), fi1(Xwi)pi 递推关系式分析向后处理法fi(X)max fi1(X), fi1(Xwi)pi 56函数描述 为了求解出fn(M)，必须从f0(X)开始，根据递推关系式进行计算。 例：n3，(p1,p2,p3)(1,2,

45、5)，(w1,w2,w3)(2,3,4)，M6(1) f0(X) X0时， f0(X) X0时， f0(X)0(2) f1(X) X0时，f1(X) 0X2时，f1(X)maxf0(X), f0(X2)1max0, 10 X2时，f1(X)maxf0(X), f0(X 2)1max0, 011f1(X) X0 1 X2 0 0X2f0(X) = X00 X0fi(X)max fi1(X), fi1(Xwi)pi 57(3) f2(X) X0 时，f2(X) 0X2时，f2(X)maxf1(X), f1(X3)2max0, 20 2X3时，f2(X)maxf1(X), f1(X3)2max1,

46、2 1 3X5时，f2(X)maxf1(X), f1(X3)2max1, 02 2 X5 时，f2(X)maxf1(X), f1(X3)2max1, 12 3f2(X) X0 max1, 123 X5max1, 022 3 X 50 0X 21 2 X 3例：n3，(p1,p2,p3)(1,2,5)，(w1,w2,w3)(2,3,4)，M6f1(X) X0 1 X2 0 0X258f3(X)maxf2(X), f2(X4)5max3, 156f2(X)maxf1(X), f1(X3)2max1, 21f1(X)maxf0(X), f0(X2)1max0, 011X31X20X11最优决策序列为

47、：(x1,x2,x3)(1,0,1)(4) f3(X) f3(M)f3(6)maxf2(6), f2(64)2max3 , 15 6基于函数表示求最优决策序列：f2(X) X0 max1, 123 X5max1, 022 3 X 50 0X 21 2 X 359图解法求解 fi1(Xwi)pi的图像可由fi1(X)在x轴上右移wi个单位，然后上移pi个单位得到。 fi(X)的图像由fi1(X)和fi1(Xwi)pi 的函数曲线按X相同时取最大值的规则归并而成。60fi1(Xwi)pifi(X)i0：函数不存在f0(X)0i1：f0(X2)1f1(X)f0(X) X00 X0f1(X) X0 m

48、ax0, 011 X2max0,10 0X2 1 2 3 4 5 6 2 1 1 2 3 4 5 6 2 1 1 2 3 4 5 6 2 1实例：n3，(w1,w2,w3)(2,3,4)，(p1,p2,p3)(1,2,5)，M=661f2(X) X0 max1,123 X5max1,022 3X50 0X21 2X3f1(X) 1 2 3 4 5 6 2 1 1 2 3 4 5 6 3 2 1i2：f1(X3)2f2(X) 1 2 3 4 5 6 3 2 162- X0 max0, -+5= 0 0X2 max1, -+5= 1 2X3 max2, -+5 = 2 3X4 max2 , 0 +

49、 5 = 5 4X5 max3 , 0 + 5 = 5 5X6 max3 , 1 + 5 = 6 6X7 max3 , 2 + 5 = 7 7X9 max3 , 3 + 5 = 8 X9 f3(X) = 1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1 1 2 3 4 5 6 3 2 1f2(X)i3：f2(X4)5f3(X)63图解法分析f2(X) 1 2 3 4 5 6 3 2 13X5，fi(X)fi(3)2X5，有fi(X)fi(5)3有r3次阶跃，有3对序偶：(P1,W1)(1,2), (P2,W2

50、)(2,3), (P3,W3)(3,5)；f2是由序偶 (0,0),(1,2), (2,3), (3,5)组成的集合所说明WP 每一个fi 完全由一些序偶(Pj, Wj)组成的集合所说明，其中Wj 是使fi 在其处产生一次阶跃的X值，Pj fi(Wj) Pj是p1,p2, pn的某些值之和，Wj是w1,w2, wn的某些值之和。 第一对序偶(P0,W0)(0,0); 若有r 次阶跃, 就还有r 对序偶(Pj, Wj), 1jr； WjWj1，则有PjPj1 0jr时，当WjXWj1，有fi(X)fi(Wj)； XWr，有fi(X)fi(Wr)64设Si1表示fi1的所有序偶的集合； Si1表示

51、fi1(Xwi)pi 的所有序偶的集合，将(pi, wi) 加到Si1的每一对序偶上就得到Si1；然后在支配规则下将Si1和Si1归并成Si 。 支配规则： 如果Si1 和 Si1中一个有(Pj,Wj)，另一个有(Pk,Wk)， 并且在WjWk的同时有PjPk， 那么，序偶(Pj,Wj) 被放弃。称为(Pk,Wk)支配(Pj,Wj)。函数 图解 序偶对65f0(X)0 1 2 3 4 5 6 2 1i1：f0(X2)1 1 2 3 4 5 6 2 1f1(X) 1 2 3 4 5 6 2 1S0(0, 0)S11(1, 2)S1(0, 0), (1, 2)S11S0(p1,w1)(0,0)(1

52、,2)(1,2)66f1(X) 1 2 3 4 5 6 2 1i2：f1(X3)2 1 2 3 4 5 6 3 2 1 1 2 3 4 5 6 3 2 1f2(X)S1(0, 0), (1, 2)S21(2, 3), (3, 5)S2(0, 0), (1, 2), (2, 3), (3, 5)S21S1(p2,w2)(0,0), (1,2)(2,3)(2,3), (3,5)67 1 2 3 4 5 6 3 2 1f2(X)S2=(0, 0), (1, 2), (2, 3), (3, 5) 1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1i3：f2(X4)5 1 2 3 4 5

53、 6 7 8 9 8 7 6 5 4 3 2 1f3(X)S31=(5,4), (6,6), (7,7), (8,9)S3 =(0,0),(1,2),(2,3),(5,4), (6,6),(7,7),(8,9)68例: S2(0,0),(1,2),(2,3),(3,5) S31(5,4),(6,6),(7,7),(8,9)S3=(0,0), (1,2), (2,3), (5,4), (6,6), (7,7), (8,9)根据支配规则，54且35，所以序偶(3, 5)被舍弃。支配规则： 如果Si1 和 Si1中一个有(Pj,Wj)，另一个有(Pk,Wk)， 并且在WjWk的同时有PjPk， 那么

54、，序偶(Pj,Wj) 被放弃。称为(Pk,Wk)支配(Pj,Wj)。69基于动态规划的向后处理法求解0/1背包问题序偶对方法 设Si1表示由x1, x2, xi1的2i1个决策序列中一些可能的序列所产生的序偶(Pj , Wj)集合。 S0(0,0) i 1时，将(pi, wi)加到Si1的每一对序偶上就得到Si1， 即 Si1= (p, w)|(ppi, wwi) Si1 在支配规则下将Si1和Si1归并成Si。在生成Si时，将WM的那些序偶(p,w)去掉，它们不能导出满足约束条件的可行解。这样生成的Si的所有序偶是背包问题KNAP(1,i,X)在0XM各种情况下的最优解。KNAP(1,n,M

55、)的最优解fn(M)由Sn的最后一对序偶的p值给出。70序偶对方法实例S0(0,0)S11(1,2)(p1,w1)(1,2)S1(0,0),(1,2)(p2,w2)(2,3)S21(2,3),(3,5)S2(0,0),(1,2),(2,3),(3,5)(p3,w3)(5,4)S31(5,4),(6,6),(7,7),(8,9)S3(0,0),(1,2),(2,3),(5,4),(6,6)根据支配规则，54且35，所以序偶(3, 5)被舍弃。wM的序偶对不会产生满足约束条件的可行解，舍弃掉。实例：n3，(w1,w2,w3)(2,3,4)，(p1,p2,p3)(1,2,5)，M=671确定决策序列

56、 若(pl, wl) Sn1，且(plpn, wlwn)Sn1，则xn1； 再判断留在Sn1的序偶(pl, wl)或(plpn, wlwn)是否属于Sn2以确定xn1的取值。 若(pl, wl)Sn1，则xn0；S1 (0,0) S1 (0,0),(1,2) S2 (0,0),(1,2),(2,3),(3,5)S3 (0,0),(1,2),(2,3),(5,4),(6,6) 如果已找到 Sn 的最末序偶(pl, wl), 那么使pi xipl , wixi wl 的x1, , xn的决策值可通过检索 Si 来确定。最优解fn(M)的最优决策序列是(x1,x2,x3)(1,0,1)x31x20

57、x11实例：n3，(w1,w2,w3)(2,3,4)，(p1,p2,p3)(1,2,5)，M672procedure DKP(p,w,n,M)S0(0,0)for i 1 to n1 do Si1 (pl,wl)|(plpi, wlwi)Si1 and wlM Si MERGE_PURGE(Si1,Si1)repeat(pX, wX)Sn1的最末序偶(pY, wY)(plpn, wlwn) 其中wl 是Sn1中使得wwnM的所有序偶中取最大值的wlif pXpY then xn0 /pX是Sn的最末序偶 else xn1 /pY是Sn的最末序偶沿Sn1, , S1回溯确定xn1,x1的值end

58、 DKP算法6.6 0/1背包问题非形式化的DKP算法S1 (0,0),(1,2) S2 (0,0),(1,2),(2,3),(3,5)(pX,wX)(3,5)(p3,w3)(5,4) , Wl=2(pY,wY)(15,24)=(6,6)(pX3)Py then xn 0 /Px是Sn的最末序偶/ else xn 1 /Py是Sn的最末序偶/endif沿Sn1, , S1回溯确定xn1, , x1的值end DKPS1 (0,0),(1,2) S2 (0,0),(1,2),(2,3),(3,5)(Px,Wx)(3,5)(p3,w3) (5,4) , Wl 2(Py,Wy)(15,24)(6,6

59、)(Px3)(Py6)所以x31算法6.6 0/1背包问题非形式化的DKP算法74DKP算法的实现思想一维数组p(n)表示物品的效益值。一维数组w(n)表示表示物品的质量。一维数组P(m)和W(m)表示序偶对(pl ,wl)，模拟序偶集合S。序偶集S0,S1,Sn1互相邻接的存放。一维数组F(0:n)是指针数组，元素Fi指示Si中的第一个元素所在的位置。在Si1中序偶是按P和W的递增次序排列的，因此Si的序偶也按这种次序生成。在生成Si1的过程中，同时将Si1和Si1按支配规则进行归并而生成Si，因此不需要附加空间存放Si1 。75DKP算法的实现思想S0 (0,0) S1 (0,0),(1,

60、2)S2 (0,0),(1,2),(2,3),(3,5)1234567800101230020235 PWF0F1F3F2初始化S0从1至n1求Si由Sn1求Sn的最末序偶回溯构造最优决策序列760/1背包问题DKP算法的实现F(i)：Si中第一对序偶在数组中的位置(下标)l, h：Si-1的第一对序偶和最后一对序偶在数组中的位置,即F(i1)和F(i)1.k: Si1中当前要加入Si的序偶的位置.u: 在Si-1能够产生Si1序偶的最后一个位置，即对于u+1v h的序偶(Pv,Wv)，有Wv+wiM.j: 当前正在生成Si1的Si1中序偶的位置.next: Si中要加入序偶的位置.77算法思