算法與設(shè)計：動態(tài)規(guī)劃法

1、算法設(shè)計與分析,2010-2011學年 第2學期,第3章 動態(tài)規(guī)劃法,本 章 目 錄,返回,3.1 概 述,3.2 圖問題中的動態(tài)規(guī)劃法,3.3 組合問題中的動態(tài)規(guī)劃法,3.4 查找問題中的動態(tài)規(guī)劃法,3.1 概 述,3.1.2 最優(yōu)化問題,3.1.3 最優(yōu)性原理,3.1.4 動態(tài)規(guī)劃法的設(shè)計思想,返回,3.1.1 動態(tài)規(guī)劃法簡介,動態(tài)規(guī)劃法與分治法類似，其基本思想也是將待求解的問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。,3.1.1 動態(tài)規(guī)劃法簡介,與分治法不同的是，適合用動態(tài)規(guī)劃求解的問題，經(jīng)分解得到的子問題往往不是互相獨立的。若用分治法解這類問題，則分解得到

2、的子問題太多，以致于最后解決原問題需要耗費指數(shù)時間。在用分治求解時，有些子問題被重復計算了多次。如果能夠保存已解決的子問題的答案。在需要的時候再找出已求的答案，就可以避免大量的重復計算，從而簡化了算法。為了達到這個目的，可以用一個表來記錄所有已解決的子問題答案。不管該子問題以后是否被用到，只要他被計算過，就將其結(jié)果填入表中。這就是動態(tài)規(guī)劃法的基本思想。,圖中每個頂點代表一個城市，兩個城市間的連線代表道路，連線上的數(shù)值代表道路的長度?，F(xiàn)在，想從城市A到達城市E，怎樣走路程最短，最短路程的長度是多少?,多階段決策過程最優(yōu)化問題,最短路徑的特性:最短路徑的第k階段通過Xk 點，則這一最短路徑在由Xk

3、 出發(fā)到終點的那一部分路徑，對于起始點為Xk 到終點的所有可能的路徑來說必定也是路徑最短的.,利用倒推方法求解A到E的最短距離。把從A到E的全過程分成四個階段，用k表示階段變量，第1階段有一個初始狀態(tài)A，兩條可供選擇的支路ABl、AB2；第2階段有兩個初始狀態(tài)B1、B2，B1有三條可供選擇的支路，B2有兩條可供選擇的支路。用dk( xk，xk+1 )表示在第k階段由初始狀態(tài)xk 到下階段的初始狀態(tài)xk+1的路徑距離，F(xiàn)k(xk)表示從第k階段的xk 到終點E的最短距離。,求從A到E的最短路問題Fk(A) ，可以轉(zhuǎn)化為兩個性質(zhì)完全相同，但規(guī)模較小的問題，即分別從B1、B2到E的最短路問題Fk(B

4、1)和Fk(B2)，這時有： Fk(A)=mind1(A,B1)+ Fk(B1),d1(A,B2)+ Fk(B2) 同樣， 計算Fk(B1) ，又可以轉(zhuǎn)化為性質(zhì)完全相同，但規(guī)模更小的問題，即分別從C1、C2、C3到E的最短路問題Fk(C1)、 Fk(C2)和 Fk(C3)，最后，歸結(jié)為Fk(D1)、 Fk(D2)兩個子問題。由于Fk(D1)、 Fk(D2)是已知的，因此，可以從這兩個值開始，逆向遞歸計算出Fk(A)的值。最終，可以得到從A到E的最短路徑。 動態(tài)規(guī)劃法就是根據(jù)最優(yōu)性原理，以自底向上的方式從子問題的最優(yōu)解逐步構(gòu)造出整個問題的最優(yōu)解。（逆向遞歸的方法）,S1：K=4，有： F4(D1

5、)=3，F(xiàn)4(D2)=4，F(xiàn)4(D3)=3 S2: K=3，有： F3(C1)=mind3(C1,D1)+F4(D1),d3(C1,D2)+F4(D2) =min8,10=8 F3(C2)=d3(C2,D1)+F4(D1)=5+3=8 F3(C3)=d3(C3,D3)+F4(D3)=8+3=11 F3(C4)=d3(C4,D3)+F4(D3)=3+3=6 S2: K=2，有： F2(B1)=mind2(B1,C1)+F3(C1),d2(B1,C2)+F3(C2),d2(B1,C3) +F3(C3)=min9,14,14=9 F2(B2)=mind2(B2,c2)+F3(C2),d2(B2,C4

6、)+F3(C4) =min16,10=10 S4：k=1，有： F1( A)=mind1(A,B1)+F2(B1),d1(A,B2)+F2(B2) =min14,13=13 因此由A到E的全過程的最短路徑為 AB2一C4D3E, 最短路程長度為13。,數(shù)塔問題 有形如圖所示的一個數(shù)塔，從頂部出發(fā)，在每一結(jié)點可以選擇向左走或是向右走，一直走到底層，要求找出一條路徑，使路徑上的數(shù)值和最大。,算法設(shè)計過程如下： 1.階段劃分： 第一步對于第五層的數(shù)據(jù)，我們做如下決策： 對經(jīng)過第四層2的路徑選擇第五層的19， 對經(jīng)過第四層18的路徑選擇第五層的10， 對經(jīng)過第四層9的路徑也選擇第五層的10， 對經(jīng)過第

7、四層5的路徑選擇第五層的16。,以上的決策結(jié)果將五階數(shù)塔問題變?yōu)?階子問題，遞推出第四層與第五層的和為: 21(2+19),28(18+10),19(9+10),21(5+16)。 用同樣的方法還可以將4階數(shù)塔問題,變?yōu)?階數(shù)塔問題。 最后得到的1階數(shù)塔問題，就是整個問題的最優(yōu)解。,2存儲、求解： 1) 原始信息存儲 原始信息有層數(shù)和數(shù)塔中的數(shù)據(jù)，層數(shù)用一個整型變量 n 存儲，數(shù)塔中的數(shù)據(jù)用二維數(shù)組data，存儲成如下的下三角陣: 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16,2) 動態(tài)規(guī)劃過程存儲 用二維數(shù)組d存儲各階段的決策結(jié)果。二維數(shù)組d的存儲內(nèi)容如下： dn

8、j=datanj j=1,2,n； dij=max(di+1j，di+1j+1)+dataij i=n-1,n-2,1，j=1,2,i； 最后d11存儲的就是問題的結(jié)果。,數(shù)組data 數(shù)組d 9 59 12 15 50 49 10 6 8 38 34 29 2 18 9 5 21 28 19 21 19 7 10 4 16 19 7 10 4 16 數(shù)塔及動態(tài)規(guī)劃過程數(shù)據(jù),輸出data11 9 b=d11-data11=59-9=50 b與d21,d22比較,b與d21相等輸出data2112 b=d21-data21=50-12=38 b與d31,d32 比較b與d31相等輸出data31

9、10 b=d31-data31=38-10=28 b與d41,d42 比較b與d42相等輸出data4218 b=d42-data42=28-18=10 b與d52,d53 比較b與d53相等輸出data5310“,3) 最優(yōu)解路徑求解及存儲,為了設(shè)計簡潔的算法，用三維數(shù)組a50503存儲以上確定的三個數(shù)組的信息。 a50501代替數(shù)組data， a50502代替數(shù)組d, a50503記錄解路徑。,for (i=n-1 ; i=1; i-) for (j=1; jai+1j+12) aij2=aij2+ai+1j2; aij3=0; else aij2=aij2+ai+1j+12; aij3=

10、1; ,cout; j=j+aij3; coutanj1;,返回,最優(yōu)化問題：有n個輸入，它的解由這n個輸入的一個子集組成，這個子集必須滿足某些事先給定的條件，這些條件稱為約束條件，滿足約束條件的解稱為問題的可行解。滿足約束條件的可行解可能不只一個，為了衡量這些可行解的優(yōu)劣，事先給出一定的標準，這些標準通常以函數(shù)的形式給出，這些標準函數(shù)稱為目標函數(shù)，使目標函數(shù)取得極值（極大或極小）的可行解稱為最優(yōu)解，這類問題就稱為最優(yōu)化問題。,3.1.2 最優(yōu)化問題,例：付款問題： 超市的自動柜員機（POS機）要找給顧客數(shù)量最少的現(xiàn)金。 假定POS機中有n張面值為pi(1in)的貨幣，用集合P=p1, p2,

11、 , pn表示，如果POS機需支付的現(xiàn)金為A，那么，它必須從P中選取一個最小子集S，使得,如果用向量X=( x1, x2, , xn)表示S中所選取的貨幣，則 （式3.2）,（式3.1）,那么，POS機支付的現(xiàn)金必須滿足 （式3.3）,并且 （式3.4）,在付款問題中，集合P是該問題的輸入，滿足式2.1的解稱為可行解，式3.2是解的表現(xiàn)形式，因為向量X中有n個元素，每個元素的取值為0或1，所以，可以有2n個不同的向量，所有這些向量的全體構(gòu)成該問題的解空間，式3.3是該問題的約束條件，式3.4是該問題的目標函數(shù)，使式3.4取得極小值的解稱為該問題的最優(yōu)解。,返回,3.1.3 最優(yōu)性原理,對于一個

12、具有n個輸入的最優(yōu)化問題，其求解過程往往可以劃分為若干個階段，每一階段的決策僅依賴于前一階段的狀態(tài)，由決策所采取的動作使狀態(tài)發(fā)生轉(zhuǎn)移，成為下一階段決策的依據(jù)。從而，一個決策序列在不斷變化的狀態(tài)中產(chǎn)生。這個決策序列產(chǎn)生的過程稱為多階段決策過程。,在每一階段的決策中有一個賴以決策的策略或目標，這種策略或目標是由問題的性質(zhì)和特點所確定，通常以函數(shù)的形式表示并具有遞推關(guān)系，稱為動態(tài)規(guī)劃函數(shù)。,多階段決策過程滿足最優(yōu)性原理（Optimal Principle）：無論決策過程的初始狀態(tài)和初始決策是什么，其余的決策都必須相對于初始決策所產(chǎn)生的當前狀態(tài)，構(gòu)成一個最優(yōu)決策序列。 如果一個問題滿足最優(yōu)性原理通常稱

13、此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。,返回,3.1.4 動態(tài)規(guī)劃法的設(shè)計思想,動態(tài)規(guī)劃法將待求解問題分解成若干個相互重疊的子問題，每個子問題對應決策過程的一個階段，一般來說，子問題的重疊關(guān)系表現(xiàn)在對給定問題求解的遞推關(guān)系（也就是動態(tài)規(guī)劃函數(shù)）中，將子問題的解求解一次并填入表中，當需要再次求解此子問題時，可以通過查表獲得該子問題的解而不用再次求解，從而避免了大量重復計算。,動態(tài)規(guī)劃法的求解過程,n=5時分治法計算斐波那契數(shù)的過程。,例：計算斐波那契數(shù)：,動態(tài)規(guī)劃法求解斐波那契數(shù)F(9)的填表過程 ：,注意到，計算F(n)是以計算它的兩個重疊子問題 F(n-1)和F(n-2)的形式來表達的，所以，可以設(shè)計一

14、張表填入n+1個F(n)的值。,用動態(tài)規(guī)劃法求解的問題具有特征： 能夠分解為相互重疊的若干子問題； 滿足最優(yōu)性原理（也稱最優(yōu)子結(jié)構(gòu)性質(zhì)）：該問題的最優(yōu)解中也包含著其子問題的最優(yōu)解。 （用反證法）分析問題是否滿足最優(yōu)性原理： 先假設(shè)由問題的最優(yōu)解導出的子問題的解不是最優(yōu)的; 然后再證明在這個假設(shè)下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導致矛盾。,動態(tài)規(guī)劃法設(shè)計算法一般分成三個階段： （1）分段：將原問題分解為若干個相互重疊的子問題； （2）分析：分析問題是否滿足最優(yōu)性原理，找出動態(tài)規(guī)劃函數(shù)的遞推式； （3）求解：利用遞推式自底向上計算，實現(xiàn)動態(tài)規(guī)劃過程。 動態(tài)規(guī)劃法利用問題的最優(yōu)性原理，以自底向上

15、的方式從子問題的最優(yōu)解逐步構(gòu)造出整個問題的最優(yōu)解。（逆向遞歸的方法）,返回,3.2 圖問題中的動態(tài)規(guī)劃法,3.2.2 TSP問題,3.2.1 多段圖的最短路徑問題,返回,3.2.1 多段圖的最短路徑問題,設(shè)圖G=(V, E)是一個帶權(quán)有向連通圖，如果把頂點集合V劃分成k個互不相交的子集Vi（2kn, 1ik），使得E中的任何一條邊(u, v)，必有uVi，vVi+m（1ik, 1i+mk），則稱圖G為多段圖，稱sV1為源點，tVk為終點。多段圖的最短路徑問題是求從源點到終點的最小代價路徑。,由于多段圖將頂點劃分為k個互不相交的子集，所以，多段圖劃分為k段，每一段包含頂點的一個子集。不失一般性，

16、將多段圖的頂點按照段的順序進行編號，同一段內(nèi)頂點的相互順序無關(guān)緊要。假設(shè)圖中的頂點個數(shù)為n，則源點s的編號為0，終點t的編號為n-1，并且，對圖中的任何一條邊(u, v)，頂點u的編號小于頂點v的編號。,設(shè)s, s1, s2, , sp, t是從s到t的一條最短路徑，從源點s開始，設(shè)從s到下一段的頂點s1已經(jīng)求出，則問題轉(zhuǎn)化為求從s1到t的最短路徑，顯然s1, s2, , sp, t一定構(gòu)成一條從s1到t的最短路徑，如若不然，設(shè)s1, r1, r2, , rq, t是一條從s1到t的最短路徑，則s, s1, r1, r2, , rq, t將是一條從s到t的路徑且比s, s1, s2, , sp

17、, t的路徑長度要短，從而導致矛盾。所以，多段圖的最短路徑問題滿足最優(yōu)性原理。,證明多段圖問題滿足最優(yōu)性原理,對多段圖的邊(u, v)，用cuv表示邊上的權(quán)值，將從源點s到終點t的最短路徑記為d(s, t)，則從源點0到終點9的最短路徑d(0, 9)由下式確定： d(0,9)=minc01+d(1,9),c02+d(2,9),c03+d(3,9) 這是最后一個階段的決策，它依賴于d(1,9)、d(2,9)和d(3,9)的計算結(jié)果，而 d(1,9)=minc14+d(4,9), c15+d(5,9) d(2, 9)=minc24+d(4, 9), c25+d(5, 9), c26+d(6, 9)

18、 d(3, 9)=minc35+d(5, 9), c36+d(6, 9) 這一階段的決策又依賴于d(4, 9)、d(5, 9)和d(6, 9)的計算結(jié)果：,d(4, 9)=minc47+d(7, 9), c48+d(8, 9) d(5, 9)=minc57+d(7, 9), c58+d(8, 9) d(6, 9)=minc67+d(7, 9), c68+d(8, 9) 這一階段的決策依賴于d(7, 9)和d(8, 9)的計算，而d(7, 9)和d(8, 9)可以直接獲得（括號中給出了決策產(chǎn)生的狀態(tài)轉(zhuǎn)移）： d(7, 9)=c797(79) d(8, 9)=c893(89) 再向前推導，有： d

19、(6, 9)=minc67+d(7, 9), c68+d(8, 9)=min6+7, 5+3=8(68) d(5, 9)=minc57+d(7, 9), c58+d(8, 9)=min8+7, 6+3=9(58) d(4, 9)=minc47+d(7, 9), c48+d(8, 9)=min5+7, 6+3=9(48),d(3, 9)=minc35+d(5, 9), c36+d(6, 9)=min4+9, 7+8=13(35) d(2, 9)=minc24+d(4, 9), c25+d(5, 9), c26+d(6, 9)=min6+9, 7+9, 8+8=15(24) d(1, 9)=min

20、c14+d(4, 9), c15+d(5, 9)=min9+9, 8+9=17(15) d(0, 9)=minc01+d(1, 9), c02+d(2, 9), c03+d(3, 9)=min4+17, 2+15, 3+13=16(03) 最后，得到最短路徑為03589，長度為16。,S1：K=4，有： F4(D1)=3，F(xiàn)4(D2)=4，F(xiàn)4(D3)=3 S2: K=3，有： F3(C1)=mind3(C1,D1)+F4(D1),d3(C1,D2)+F4(D2) =min8,10=8 F3(C2)=d3(C2,D1)+F4(D1)=5+3=8 F3(C3)=d3(C3,D3)+F4(D3)=

21、8+3=11 F3(C4)=d3(C4,D3)+F4(D3)=3+3=6 S2: K=2，有： F2(B1)=mind2(B1,C1)+F3(C1),d2(B1,C2)+F3(C2),d2(B1,C3) +F3(C3)=min9,14,14=9 F2(B2)=mind2(B2,c2)+F3(C2),d2(B2,C4)+F3(C4) =min16,10=10 S4：k=1，有： F1( A)=mind1(A,B1)+F2(B1),d1(A,B2)+F2(B2) =min14,13=13 因此由A到E的全過程的最短路徑為 AB2一C4D3E, 最短路程長度為13。,多段圖的最短路徑問題的填表形式。

22、 用一個數(shù)組costn作為存儲子問題解的表格，costi表示從頂點i到終點n-1的最短路徑，數(shù)組pathn存儲狀態(tài)，pathi表示從頂點i到終點n-1的路徑上頂點i的下一個頂點。則： costi=mincij+costj (ijn且頂點j是頂點i的鄰接點) (式3.5) pathi=使cij+costj最小的j (式3.6）,算法多段圖的最短路徑 1初始化：數(shù)組costn初始化為最大值，數(shù)組pathn初始化為-1； 2for (i=n-2; i=0; i-) 2.1 對頂點i的每一個鄰接點j，根據(jù)式2.5計算costi; 2.2 根據(jù)式2.6計算pathi; 3輸出最短路徑長度cost0; 4

23、. 輸出最短路徑經(jīng)過的頂點： 4.1 i=0 4.2 循環(huán)直到pathi=n-1 4.2.1 輸出pathi; 4.2.2 i=pathi;,算法主要由三部分組成：第一部分是初始化部分，其時間性能為O(n)；第二部分是依次計算各個頂點到終點的最短路徑，由兩層嵌套的循環(huán)組成，外層循環(huán)執(zhí)行n-1次，內(nèi)層循環(huán)對所有出邊進行計算，并且在所有循環(huán)中，每條出邊只計算一次。假定圖的邊數(shù)為m，則這部分的時間性能是O(m)；第三部分是輸出最短路徑經(jīng)過的頂點，其時間性能是O(n)。所以，算法6.2的時間復雜性為O(n+m)。,返回,3.2.2 TSP問題,TSP問題是指旅行家要旅行n個城市，要求各個城市經(jīng)歷且僅經(jīng)

24、歷一次然后回到出發(fā)城市，并要求所走的路程最短。 各個城市間的距離可以用代價矩陣來表示。,設(shè)s, s1, s2, , sp, s是從s出發(fā)的一條路徑長度最短的簡單回路，假設(shè)從s到下一個城市s1已經(jīng)求出，則問題轉(zhuǎn)化為求從s1到s的最短路徑，顯然s1, s2, , sp, s一定構(gòu)成一條從s1到s的最短路徑。 如若不然，設(shè)s1, r1, r2, , rq, s是一條從s1到s的最短路徑且經(jīng)過n-1個不同城市，則s, s1, r1, r2, , rq, s將是一條從s出發(fā)的路徑長度最短的簡單回路且比s, s1, s2, , sp, s要短，從而導致矛盾。所以，TSP問題滿足最優(yōu)性原理。,證明TSP問題

25、滿足最優(yōu)性原理,假設(shè)從頂點i出發(fā)，令d( i, V )表示從頂點i 出發(fā)經(jīng)過V 中各個頂點一次且僅一次，最后回到出發(fā)點 i 的最短路徑長度，開始時，V V i ，于是，TSP問題的動態(tài)規(guī)劃函數(shù)為： d( i,V )=mincik+d(k,Vk)(kV ) （式3.7） d(k, )=cki(ki) （式3.8）,這是最后一個階段的決策，而： 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) 這一階段的決策又

26、依賴于下面的計算結(jié)果： 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, ),從城市0出發(fā)經(jīng)城市1、2、3然后回到城市0的最短路徑長度是： d(0,1, 2, 3)=minc01+d(1, 2, 3), c02+d(2, 1, 3), c03+d(3, 1, 2),而下式可以直接獲得（括號中是該決策引起的狀態(tài)轉(zhuǎn)移）： d(1, )=c10=5(10) d(2, )=c20=6(20) d(3, )=c30=3(30)

27、,再向前倒推，有： d(1, 2)= c12+d(2, )=2+6=8(12) d(1, 3)= c13+d(3, )=3+3=6(13) d(2, 3)= c23+d(3, )=2+3=5(23) d(2, 1)= c21+d(1, )=4+5=9(21) d(3, 1)= c31+d(1, )=7+5=12(31) d(3, 2)= c32+d(2, )=5+6=11(32) 再向前倒退，有： 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)=

28、min4+6, 2+12=10(21),d(3, 1, 2)=minc31+d(1, 2), c32+ d(2, 1)=min7+8, 5+9=14(32) 最后有： 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) 所以，從頂點0出發(fā)的TSP問題的最短路徑長度為10，路徑是01230。,假設(shè)n個頂點用0n-1的數(shù)字編號，首先生成1n-1個元素的子集存放在數(shù)組V2n-1中，設(shè)數(shù)組dn2n-1存放迭代結(jié)果，其中dij表示從頂點i經(jīng)過子集Vj中的頂點一次且僅一次

29、，最后回到出發(fā)點0的最短路徑長度。,動態(tài)規(guī)劃法求解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;,顯然，算法的時間復雜性為O(2n)。和蠻力法相比，動態(tài)規(guī)劃法求解TSP問題，把原來的時間復雜性是O(n!)

30、的排列問題，轉(zhuǎn)化為組合問題，從而降低了算法的時間復雜性，但它仍需要指數(shù)時間。,設(shè)頂點之間的代價存放在數(shù)組cnn中，動態(tài)規(guī)劃法求解TSP問題的算法如下：,返回,3.3 組合問題中的動態(tài)規(guī)劃法,3.3.1 0 / 1背包問題,3.3.2 最長公共子序列問題,返回,3.3.1 0 / 1背包問題,在0/1背包問題中，物品i或者被裝入背包，或者不被裝入背包，設(shè)xi表示物品i裝入背包的情況，則當xi=0時，表示物品i沒有被裝入背包，xi=1時，表示物品i被裝入背包。根據(jù)問題的要求，有如下約束條件和目標函數(shù)：,（式3.9）,（式3.10）,于是，問題歸結(jié)為尋找一個滿足約束條件式3.9，并使目標函數(shù)式3.1

31、0達到最大的解向量X=(x1, x2, , xn)。,證明0/1背包問題滿足最優(yōu)性原理。 設(shè)(x1, x2, , xn)是所給0/1背包問題的一個最優(yōu)解，則( x2, , xn)是下面一個子問題的最優(yōu)解：,如若不然，設(shè)(y2, , yn)是上述子問題的一個最優(yōu)解，則 因此， 這說明(x1, y2, , yn)是所給0/1背包問題比(x1, x2, , xn)更優(yōu)的解，從而導致矛盾。,0/1背包問題可以看作是決策一個序列(x1, x2, , xn)，對任一變量xi的決策是決定xi=1還是xi=0。在對xi-1決策后，已確定了(x1, , xi-1)，在決策xi時，問題處于下列兩種狀態(tài)之一： （1

32、）背包容量不足以裝入物品i，則xi=0，背包不增加價值； （2）背包容量可以裝入物品i，則xi=1，背包的價值增加了vi 這兩種情況下背包價值的最大者應該是對xi決策后的背包價值。,的最優(yōu)值為V(i，j)，即V(i，j)是背包容量為j （1jC） ，可選擇物品為i，i+1，n時0-1背包問題的最優(yōu)值。由0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計算V(i，j)的遞歸式（動態(tài)規(guī)劃函數(shù)）如下。 V(i, 0)= V(0, j)=0 （式3.11）,（式3.12）,設(shè)所給0-1背包問題的子問題,式3.11表明：把前面i個物品裝入容量為0的背包和把0個物品裝入容量為j的背包，得到的價值均為0。式3.12

33、的第一個式子表明：如果第i個物品的重量大于背包的容量，則裝入前i個物品得到的最大價值和裝入前i-1個物品得到的最大價值是相同的，即物品i不能裝入背包；第二個式子表明：如果第i個物品的重量小于背包的容量，則會有以下兩種情況： （1）如果把第i個物品裝入背包，則背包中物品的價值等于把前i-1個物品裝入容量為j-wi的背包中的價值加上第i個物品的價值vi； （2）如果第i個物品沒有裝入背包，則背包中物品的價值就等于把前i-1個物品裝入容量為j的背包中所取得的價值。 顯然，取二者中價值較大者作為把前i個物品裝入容量為j的背包中的最優(yōu)解。,根據(jù)動態(tài)規(guī)劃函數(shù)，用一個(n+1)(C+1)的二維表V，Vij表

34、示把前i個物品裝入容量為j的背包中獲得的最大價值。,例如，有5個物品，其重量分別是2, 2, 6, 5, 4，價值分別為 6, 3, 5, 4, 6，背包的容量為10。,按下述方法來劃分階段：第一階段，只裝入前1個物品，確定在各種情況下的背包能夠得到的最大價值；第二階段，只裝入前2個物品，確定在各種情況下的背包能夠得到的最大價值；依此類推，直到第n個階段。最后，V(n,C)便是在容量為C的背包中裝入n個物品時取得的最大價值。為了確定裝入背包的具體物品，從V(n,C)的值向前推，如果V(n,C)V(n-1,C)，表明第n個物品被裝入背包，前n-1個物品被裝入容量為C-wn的背包中；否則，第n個物

35、品沒有被裝入背包，前n-1個物品被裝入容量為C的背包中。依此類推，直到確定第1個物品是否被裝入背包中為止。由此，得到如下函數(shù)：,（式3.13）,設(shè)n個物品的重量存儲在數(shù)組wn中，價值存儲在數(shù)組vn中，背包容量為C，數(shù)組Vn+1C+1存放迭代結(jié)果，其中Vij表示前i個物品裝入容量為j的背包中獲得的最大價值，數(shù)組xn存儲裝入背包的物品，動態(tài)規(guī)劃法求解0/1背包問題的算法如下：,算法0/1背包問題 int KnapSack(int n, int w , int v ) for (i=0; i0; i-) if (VijVi-1j) xi=1; j=j-wi; else xi=0; return Vn

36、C; /返回背包取得的最大價值 ,在算法中，第一個for循環(huán)的時間性能是O(n)，第二個for循環(huán)的時間性能是O(C)，第三個循環(huán)是兩層嵌套的for循環(huán)，其時間性能是O(nC)，第四個for循環(huán)的時間性能是O(n)，所以，算法6.3的時間復雜性為O(nC)。,返回,3.3.2 最長公共子序列問題,對給定序列X=(x1, x2, xm)和序列Z=(z1, z2, zk)，Z是X的子序列當且僅當存在一個嚴格遞增下標序列(i1, i2, ik)，使得對于所有j=1, 2, , k，有zj=xij（1ijm）。 給定兩個序列X和Y，當另一個序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子

37、序列。最長公共子序列問題就是在序列X和Y的公共子序列中查找長度最長的公共子序列。,證明最長公共子序列問題滿足最優(yōu)性原理。 設(shè)序列X=x1, x2, xm和Y=y1, y2, yn的最長公共子序列為Z=z1, z2, zk，記Xk為序列X中前k個連續(xù)字符組成的子序列，Yk為序列Y中前k個連續(xù)字符組成的子序列，Zk為序列Z中前k個連續(xù)字符組成的子序列，顯然有下式成立： （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的最長公共子序列。 可見，兩個

38、序列的最長公共子序列包含了這兩個序列的前綴序列的最長公共子序列。,要找出序列X=x1, x2, xm和Y=y1, y2, yn的最長公共子序列，可按下述遞推方式計算：當xm=yn時，找出Xm-1和Yn-1的最長公共子序列，然后在其尾部加上xm即可得到X和Y的最長公共子序列；當xmyn時，必須求解兩個子問題：找出Xm-1和Y的最長公共子序列以及Xm和Yn-1的最長公共子序列，這兩個公共子序列中的較長者即為X和Y的最長公共子序列。用Lij表示子序列Xi和Yj的最長公共子序列的長度，可得如下動態(tài)規(guī)劃函數(shù)： L00=Li0=L0j=0(1im,1jn) （式3.14） （式3.15）,由此，把序列X=

39、x1, x2, xm和Y=y1, y2, yn的最長公共子序列的搜索分為m個階段，第1階段，按照式3.15計算X1和Yj的最長公共子序列長度L1j（1jn），第2階段，按照式3.15計算X2和Yj的最長公共子序列長度L2j（1jn），依此類推，最后在第m階段，計算Xm和Yj的最長公共子序列長度Lmj（1jn），則Lmn就是序列Xm和Yn的最長公共子序列的長度。,為了得到序列Xm和Yn具體的最長公共子序列，設(shè)二維表Sm+1n+1，其中Sij表示在計算Lij的過程中的搜索狀態(tài)，并且有：,（式3.16）,若Sij=1，表明ai=bj，則下一個搜索方向是Si-1j-1；若Sij=2，表明aibj且Li

40、j-1Li-1j，則下一個搜索方向是Sij-1；若Sij=3，表明aibj且Lij-1Li-1j，則下一個搜索方向是Si-1j。,(a) 長度矩陣L (b) 狀態(tài)矩陣S,例：序列X=(a, b, c, b, d, b)，Y=(a, c, b, b, a, b, d, b, b)，建立兩個(m+1)(n+1)的二維表L和表S，分別存放搜索過程中得到的子序列的長度和狀態(tài)。,算法最長公共子序列問題 int CommonOrder(int m, int n, int x , int y , int z ) for (j=0; j=Li-1j) Lij=Lij-1; Sij=2; else Lij=Li

41、-1j; Sij=3; i=m; j=n; k=Lmn; for (i0 ,第一個for循環(huán)的時間性能是O(n)； 第二個for循環(huán)的時間性能是O(m)； 第三個循環(huán)是兩層嵌套的for循環(huán)，其時間性能是O(mn)； 第四個for循環(huán)的時間性能是O(k)，而kminm, n，所以，算法6.4的時間復雜性是O(mn)。,返回,設(shè)r1, r2, , rn是n個記錄的集合，其查找概率分別是p1, p2, , pn，最優(yōu)二叉查找樹（Optimal Binary Search Trees）是以這n個記錄構(gòu)成的二叉查找樹中具有最少平均比較次數(shù)的二叉查找樹，即 最小，其中pi是記錄ri的查找概率，ci是在二叉查找樹中查找ri的比較次數(shù)。,最優(yōu)二叉查找樹,3.4 查找問題中的動態(tài)規(guī)劃法,返回,例如，集合A, B, C, D的查找概率是0.1, 0.2, 0.4, 0.3， (a)的平均比較次數(shù)是0.110.22+0.43+0.34=2.9， (b)的平均比較次數(shù)是0.120.21+0.42+0.33=2.1， (c)的平均比較次數(shù)是0