第3章 動(dòng)態(tài)規(guī)劃3_0-1背包問題

1、 (Dynamic Programming) 0-1背包問題問題描述： 給定n種物品和一背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。問應(yīng)如何選擇裝入背包中的物品，使得裝入背包中物品的總價(jià)值最大？0-1背包問題： 對(duì)每種物品i裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。 0-1背包問題(3.4.1) max 1niiixv1. . 0,1,1niiiiw xCstxin 給定給定n n種物品和一背包。物品種物品和一背包。物品i i的重量是的重量是w wi i，其價(jià)值為，其價(jià)值為v vi i，背包的容量為背包的容量為C C。問。問: :應(yīng)如何選擇裝入背包的

2、物品，使得裝應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大入背包中物品的總價(jià)值最大? ?0-1背包問題描述背包問題描述:給定給定C 0, w wi i 0, v vi i 0 , 1in.要求找一要求找一n元向量元向量(x1 1,x2 2,xn n), xi i0,1, w wi i xi iC,且且 v vi i xi i達(dá)最大達(dá)最大, ,即即一個(gè)特殊的整數(shù)規(guī)劃問題。一個(gè)特殊的整數(shù)規(guī)劃問題。 1.最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì) 最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì):設(shè)設(shè)(y1,y2,yn)是是 (3.4.1)的一個(gè)最優(yōu)解，則的一個(gè)最優(yōu)解，則(y2,yn)是下面相應(yīng)子問題的一個(gè)最優(yōu)解是下面相應(yīng)

3、子問題的一個(gè)最優(yōu)解: niiixv2max112s.t. 0,1, 2niiiiw xCw yxin 證明證明:使用反證法使用反證法. 若不然若不然,設(shè)設(shè)(z2,z3,zn)是上述子問題的一個(gè)最優(yōu)解是上述子問題的一個(gè)最優(yōu)解,而而(y2,y3,yn)不是它的最優(yōu)解不是它的最優(yōu)解.顯然有顯然有 vizi viyi (i=2,n)且且 w1y1+ wizi C因此因此 v1y1+ vizi (i=2,n) viyi, (i=1,n) 說明說明(y1,z2, z3,zn)是是(3-4-1)0-1背包問題的一個(gè)更優(yōu)解背包問題的一個(gè)更優(yōu)解,導(dǎo)出導(dǎo)出(y1,y2,yn)不是背包問題的最優(yōu)解不是背包問題的最優(yōu)

4、解,矛盾矛盾. 2.遞歸關(guān)系遞歸關(guān)系 設(shè)所給設(shè)所給0-1背包問題的子問題背包問題的子問題(3.4.2) nikkkxvmax nkixjxwtsknikkk,.10 的的最優(yōu)值為最優(yōu)值為m(i，j)，即，即m(i，j)是背包容量為是背包容量為j，可選擇物品為，可選擇物品為i，i+1，n時(shí)時(shí)0-1背包問題的最優(yōu)值。背包問題的最優(yōu)值。 2.遞歸關(guān)系遞歸關(guān)系由由0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算m(i，j)的遞歸式如下：的遞歸式如下： iiiiwjwjjimvwjimjimjim0), 1(), 1(), 1(max),(第第i個(gè)物品不裝入背包個(gè)物品不

5、裝入背包第第i個(gè)物品裝入背包個(gè)物品裝入背包第第i個(gè)物品無法裝入背包個(gè)物品無法裝入背包 (1)( , ) (3.4.4)0 (2)0nnnjwvm n jjw(3.4.3)課本P76有誤！ 注注:(3-4-3)式式 此時(shí)背包容量為此時(shí)背包容量為j，可選擇物品為，可選擇物品為i。此時(shí)在對(duì)。此時(shí)在對(duì)xi作出決策之后作出決策之后,問題處于兩種狀態(tài)之一問題處于兩種狀態(tài)之一:背包剩余容量是背包剩余容量是j,沒產(chǎn)生任何效益沒產(chǎn)生任何效益;剩余容量剩余容量j-wi,效益值增長了效益值增長了vi .從從n推至推至i+1, i算出最優(yōu)值算出最優(yōu)值m(i, j) （ i=n,1） 。 m(1,C)為最優(yōu)值。為最優(yōu)值

6、。然后用算法然后用算法traceback找出最優(yōu)解找出最優(yōu)解xi ，其中其中i，C為整值。為整值。)3 . 4 . 3( (2) 0(1) ), 1(), 1(), 1(max),(iiiiwjwjjimvwjimjimjim(3.4.4) (2) 0(1) 0),(nnnwjwjvjnm2.遞歸關(guān)系遞歸關(guān)系 3.算法描述算法描述void knapsack( int v, int w, int c, int m) int n = v.length-1; int jMax = min(wn-1, c) /背包剩余容量背包剩余容量/ for(int j = 0; j=jMax; j+) /背包裝不

7、下背包裝不下wn的情況的情況/ mnj=0; for(int j=wn; j1; i-) jMax=min(wi-1, c); for(int j=0; j=jMax; j+) /背包裝不下背包裝不下wi的情況的情況/ mij=mi+1j; /沒產(chǎn)生任何效益沒產(chǎn)生任何效益/ for(int j=wi; j=w1) /如果背包裝得下如果背包裝得下w1/ m1c=max(m1c, m2c-w1+v1);void traceback(int m, int w, int c, int x) /求最優(yōu)解求最優(yōu)解xi / int n = w.length-1; for(int i=1; i0)?1:0;說

8、明說明:當(dāng)當(dāng)wi為正整數(shù)時(shí)，用二維數(shù)組為正整數(shù)時(shí)，用二維數(shù)組m來存儲(chǔ)來存儲(chǔ)m(i,j)相應(yīng)的相應(yīng)的最優(yōu)值。最優(yōu)值。knapsack算法的算法的一個(gè)缺點(diǎn)是要求一個(gè)缺點(diǎn)是要求所給物品的重量所給物品的重量w wi i（1 1 i i n n）是整數(shù)是整數(shù) )3 . 4 . 3( (2) 0(1) ), 1(), 1(), 1(max),(iiiiwjwjjimvwjimjimjim(3.4.4) (2) 0(1) 0),(nnnwjwjvjnm算法復(fù)雜度分析：算法復(fù)雜度分析：從從m(i，j)的遞歸式容易看出，算法的遞歸式容易看出，算法knapsack需需要要O(nc)計(jì)算時(shí)間計(jì)算時(shí)間; traceb

9、ack需需O(n)計(jì)算時(shí)間計(jì)算時(shí)間 ；算法總體需要算法總體需要O(nc)計(jì)算時(shí)間。計(jì)算時(shí)間。當(dāng)背包容量當(dāng)背包容量c很很大時(shí)，算法需要的計(jì)算時(shí)間較多。例如，當(dāng)大時(shí)，算法需要的計(jì)算時(shí)間較多。例如，當(dāng)c2n時(shí)，算法需要時(shí)，算法需要(n2n)計(jì)算時(shí)間。計(jì)算時(shí)間。 4.算法復(fù)雜度分析算法復(fù)雜度分析 0-1背包問題 012345678910 w1=2 v1=61w2=2 v2=32w3=6 v3=53w4=5 v4=44w5=4 v5=65 0問題實(shí)例問題實(shí)例： 有5個(gè)物品，其重量分別是2, 2, 6, 5, 4，價(jià)值分別為6, 3, 5, 4, 6，背包的容量為10。 0-1背包問題 012345678

10、910 w1=2 v1=61w2=2 v2=32w3=6 v3=53w4=5 v4=44w5=4 v5=65 0問題實(shí)例： 有5個(gè)物品，其重量分別是2, 2, 6, 5, 4，價(jià)值分別為6, 3, 5, 4, 6，背包的容量為10。0 00 00 00 06 66 66 66 66 66 66 6m5=4=6m5=4=6 0-1背包問題 012345678910 w1=2 v1=61w2=2 v2=32w3=6 v3=53w4=5 v4=44w5=4 v5=65 0問題實(shí)例： 有5個(gè)物品，其重量分別是2, 2, 6, 5, 4，價(jià)值分別為6, 3, 5, 4, 6，背包的容量為10。0 00

11、00 00 06 66 666610100 00 00 00 06 66 66 66 66 66 66 6+v4容量為容量為5 5的背包，考慮是否裝入物品的背包，考慮是否裝入物品4 4 0-1背包問題 012345678910 w1=2 v1=61w2=2 v2=32w3=6 v3=53w4=5 v4=44w5=4 v5=65 0問題實(shí)例： 有5個(gè)物品，其重量分別是2, 2, 6, 5, 4，價(jià)值分別為6, 3, 5, 4, 6，背包的容量為10。0 00 06 66 69 99 9121212121515151515150 00 03 33 36 66 69 99 99 9101011110

12、 00 00 00 06 66 66 66 66 6101011110 00 00 00 06 66 66 66 66 6101010100 00 00 00 06 66 66 66 66 66 66 6 0-1背包問題統(tǒng)計(jì)結(jié)果：問題實(shí)例： 有5個(gè)物品，其重量分別是2, 2, 6, 5, 4，價(jià)值分別為6, 3, 5, 4, 6，背包的容量為10。 5改進(jìn)算法改進(jìn)算法 為克服以上缺點(diǎn)，引入階梯函數(shù)。利用序偶概念，改進(jìn)為克服以上缺點(diǎn)，引入階梯函數(shù)。利用序偶概念，改進(jìn)算法的計(jì)算時(shí)間復(fù)雜性為算法的計(jì)算時(shí)間復(fù)雜性為O(2n )。而當(dāng)所給物品的重量。而當(dāng)所給物品的重量wi是是整數(shù)時(shí)，其計(jì)算時(shí)間復(fù)雜性為整

13、數(shù)時(shí)，其計(jì)算時(shí)間復(fù)雜性為 （略）（略） 。 動(dòng)態(tài)規(guī)劃的其他應(yīng)用實(shí)例（略）動(dòng)態(tài)規(guī)劃的其他應(yīng)用實(shí)例（略） 凸多邊形最優(yōu)三角剖分凸多邊形最優(yōu)三角剖分 多邊形游戲多邊形游戲 圖像壓縮圖像壓縮 電路布線電路布線 流水作業(yè)調(diào)度流水作業(yè)調(diào)度 最優(yōu)二叉搜索樹最優(yōu)二叉搜索樹(min,2 )nOnc 總總 結(jié)結(jié) 動(dòng)態(tài)規(guī)劃算法適用于解最優(yōu)化問題。動(dòng)態(tài)規(guī)劃算法適用于解最優(yōu)化問題。通常按以下幾個(gè)步驟設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法：通常按以下幾個(gè)步驟設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法：（1 1）找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；）找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；（2 2）遞歸地定義最優(yōu)值；）遞歸地定義最優(yōu)值；（3 3）以自底向上的方式計(jì)算出最優(yōu)值

14、）以自底向上的方式計(jì)算出最優(yōu)值（4 4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。 總總 結(jié)結(jié) 動(dòng)態(tài)規(guī)劃缺陷：動(dòng)態(tài)規(guī)劃缺陷：（1 1）無一統(tǒng)一標(biāo)準(zhǔn)模型可供應(yīng)用。利用無一統(tǒng)一標(biāo)準(zhǔn)模型可供應(yīng)用。利用“最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)”得得出遞歸關(guān)系式后，必須結(jié)合問題的特點(diǎn)，結(jié)合其他數(shù)學(xué)技巧出遞歸關(guān)系式后，必須結(jié)合問題的特點(diǎn)，結(jié)合其他數(shù)學(xué)技巧求解，且無統(tǒng)一處理方法。求解，且無統(tǒng)一處理方法。（2 2）數(shù)值求解中，當(dāng)問題中的狀態(tài)變量個(gè)數(shù)太多，由于計(jì)算機(jī)數(shù)值求解中，當(dāng)問題中的狀態(tài)變量個(gè)數(shù)太多，由于計(jì)算機(jī)存儲(chǔ)量及計(jì)算速度限制而無法對(duì)付存儲(chǔ)量及計(jì)算速度限制而無法對(duì)付“維數(shù)障

15、礙維數(shù)障礙”。 總總 結(jié)結(jié) 動(dòng)態(tài)規(guī)劃的優(yōu)越之處動(dòng)態(tài)規(guī)劃的優(yōu)越之處: :（1 1）易于確定全局解。動(dòng)態(tài)規(guī)劃方法是一種逐步改善的方法，易于確定全局解。動(dòng)態(tài)規(guī)劃方法是一種逐步改善的方法，它把原問題化成一系列結(jié)構(gòu)相似的最優(yōu)化子問題，而每個(gè)子它把原問題化成一系列結(jié)構(gòu)相似的最優(yōu)化子問題，而每個(gè)子問題的變量個(gè)數(shù)比原問題少得多，約束集合也簡單得多，故問題的變量個(gè)數(shù)比原問題少得多，約束集合也簡單得多，故較易于確定全局最優(yōu)。特別當(dāng)處理離散類型問題時(shí)，動(dòng)態(tài)規(guī)較易于確定全局最優(yōu)。特別當(dāng)處理離散類型問題時(shí)，動(dòng)態(tài)規(guī)劃是求出全局最優(yōu)化解的唯一方法。劃是求出全局最優(yōu)化解的唯一方法。（2 2）能得一族解，有利分析結(jié)果是否有用或

16、進(jìn)行選擇（決策），能得一族解，有利分析結(jié)果是否有用或進(jìn)行選擇（決策），且大大節(jié)省工作量。且大大節(jié)省工作量。（3 3）能利用經(jīng)驗(yàn)，提高求解效率。動(dòng)態(tài)規(guī)劃方法反映過程逐段能利用經(jīng)驗(yàn)，提高求解效率。動(dòng)態(tài)規(guī)劃方法反映過程逐段演變的前后聯(lián)系，與實(shí)際進(jìn)程更緊密。演變的前后聯(lián)系，與實(shí)際進(jìn)程更緊密。（4 4）有廣泛應(yīng)用背景有廣泛應(yīng)用背景 對(duì)對(duì) 比比 1. 1. 分治法與動(dòng)態(tài)規(guī)劃主要共同點(diǎn)分治法與動(dòng)態(tài)規(guī)劃主要共同點(diǎn): :二者都要求原問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)二者都要求原問題具有最優(yōu)子結(jié)構(gòu)性質(zhì), ,都是將原問題分而治都是將原問題分而治之之, ,分解成若干個(gè)規(guī)模較小分解成若干個(gè)規(guī)模較小( (小到很容易解決的程序小到很容

17、易解決的程序) )的子問題的子問題. .然后將子問題的解合并然后將子問題的解合并, ,形成原問題的解形成原問題的解. . 2. 2. 分治法與動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)方法分治法與動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)方法: : 分治法通常利用遞歸求解分治法通常利用遞歸求解. . 動(dòng)態(tài)規(guī)劃通常利用動(dòng)態(tài)規(guī)劃通常利用迭代法自底向上求解迭代法自底向上求解, ,但也能用具有但也能用具有記記憶功能的遞歸法自頂向下求解（備忘錄法）憶功能的遞歸法自頂向下求解（備忘錄法）. . 3. 3. 分治法與動(dòng)態(tài)規(guī)劃主要區(qū)別分治法與動(dòng)態(tài)規(guī)劃主要區(qū)別: : 分治法將分解后的子問題看成相互獨(dú)立的分治法將分解后的子問題看成相互獨(dú)立的. . 動(dòng)態(tài)規(guī)劃將分解后的子問題理解為相互間有聯(lián)系動(dòng)態(tài)規(guī)劃將分解后的子問題理解為相互間有聯(lián)系, ,有重疊有重疊部分部分. . 對(duì)對(duì) 比比 4. 4. 分治法與動(dòng)態(tài)規(guī)劃適用條件分治法與動(dòng)態(tài)規(guī)劃適用條件: : 分治法：原問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)的前提下分治法：原問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)的前提下, ,分解出的分解出的子問題都絕對(duì)相互獨(dú)立子問題都絕對(duì)相互獨(dú)立. . 動(dòng)態(tài)規(guī)劃：原問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)的前提下動(dòng)態(tài)規(guī)劃：原問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)的前提下, ,分解出分解出的子問題并不相互獨(dú)立的子問題并不相互獨(dú)立, ,求解一個(gè)子問題可能要用到已經(jīng)求解求解一個(gè)子問題可能要用到已經(jīng)求