第六講動態(tài)規(guī)劃背包問題ppt課件

1、背包類動態(tài)規(guī)劃問題背包類動態(tài)規(guī)劃問題經(jīng)典的背包問題經(jīng)典的背包問題01背包背包q有有N件物品件物品;q第第i件物品件物品Wi公斤公斤;q第第i件物品價值件物品價值Ci元元;q現(xiàn)有一輛載重現(xiàn)有一輛載重M公斤的卡車公斤的卡車;q問選取裝載哪些物品，使得卡車運送的總價值問選取裝載哪些物品，使得卡車運送的總價值最大？最大？動態(tài)規(guī)劃q 可以按每個物品進展規(guī)劃，同樣每種物品有選和不選兩種可以按每個物品進展規(guī)劃，同樣每種物品有選和不選兩種選擇選擇q 設(shè)設(shè)F(i,j)表示前表示前i件物品載重為件物品載重為j的最大效益，那么有的最大效益，那么有q 1=i=N, 0=j=wi then /背包容量夠大 fi,j:=

2、max(fi-1,j-wi+ci,fi-1,j)else /背包容量缺乏 fi,j:=fi-1,j;end;滿背包問題滿背包問題01背包背包q有有N件物品件物品;q第第i件物品件物品Wi公斤公斤;q第第i件物品價值件物品價值Ci元元;q現(xiàn)有一輛載重現(xiàn)有一輛載重M公斤的卡車公斤的卡車;q問選取裝載哪些物品，使得卡車開車正好裝滿問選取裝載哪些物品，使得卡車開車正好裝滿時，運送的總價值最大？時，運送的總價值最大？q假設(shè)無法裝滿卡車，那么輸出無解。假設(shè)無法裝滿卡車，那么輸出無解。動態(tài)規(guī)劃q設(shè)設(shè)F(i,j)表示前表示前i件物品背包為件物品背包為j的最大效益，那么的最大效益，那么有有q1=i=N, 0=j

3、=Nq初值：初值：F(0,j)=0， F(1,j)= -qF(N,M)即答案即答案q顯然時間復(fù)雜度為顯然時間復(fù)雜度為O(NM)種物品不裝載第種物品裝載第ijiFiiCiwjiFMaxjiF), 1(,), 1(),(帶條件的背包問題帶條件的背包問題1q 有有N件物品件物品;q 第第i件物品件物品Wi公斤公斤;q 第第i件物品價值件物品價值Ci元元;q 第第i件物品能夠帶件物品能夠帶02個附件；個附件；q 假設(shè)裝載附件，必需裝載主件，反之沒有約束；假設(shè)裝載附件，必需裝載主件，反之沒有約束；q 現(xiàn)有一輛載重現(xiàn)有一輛載重M公斤的卡車公斤的卡車;q 問選取裝載哪些物品，使得卡車運送的總價值最大？問選取

4、裝載哪些物品，使得卡車運送的總價值最大？分析q 假設(shè)只需主件的情況假設(shè)只需主件的情況 ，顯然與經(jīng)典背包問題完全一樣！，顯然與經(jīng)典背包問題完全一樣！q 如今每個物品有附件，我們可以分成如今每個物品有附件，我們可以分成4種方案種方案q 僅裝載主件僅裝載主件q 裝載主件裝載主件+第第1個附件個附件q 裝載主件裝載主件+第第2個附件個附件q 裝載主件裝載主件+2個附件個附件q 由于上述由于上述4種并列，這是幾種不同的決策同時規(guī)劃即可種并列，這是幾種不同的決策同時規(guī)劃即可動態(tài)規(guī)劃q 設(shè)設(shè)F(i,j)表示前表示前i件物品背包為件物品背包為j的最優(yōu)解，那么有，的最優(yōu)解，那么有，q 1=i=N, 0=j=Mq

5、 時間復(fù)雜度時間復(fù)雜度O(NM)件附件選主件和，件附件選主件和第，件附件選主件和第，只選主件件物品不選第2/21)2-1w-, 1(2/2)2-, 1(1/1)1w-, 1(), 1(i), 1(),(iciciciwiiwjiFiciciwiwjiFiciciiwjiFiciwjiFjiFMaxjiF多層背包問題q有有N件物品件物品;q第第i件物品件物品Wi公斤公斤;q第第i件物品價值件物品價值Ci元元;q現(xiàn)有一輛載重現(xiàn)有一輛載重M公斤的卡車公斤的卡車;q第第i件物品限制最多只能取件物品限制最多只能取Xi個；個；q問選取裝載哪些物品，使得卡車運送的總價值最問選取裝載哪些物品，使得卡車運送的總

6、價值最大？大？分析q 我們可以類似我們可以類似01背包問題，將第背包問題，將第i種物品拆分成種物品拆分成xi個，個，這樣每個物品只需這樣每個物品只需1件了件了,如以下圖如以下圖:q 然后對一切的物品采用動態(tài)規(guī)劃即可。然后對一切的物品采用動態(tài)規(guī)劃即可。q F(i,j)=max f(i-1,j-k*wi) + k*ci q 0=k*wi=j完全背包問題q有有N件物品件物品;q第第i件物品件物品Wi公斤公斤;q第第i件物品價值件物品價值Ci元元;q現(xiàn)有一輛載重現(xiàn)有一輛載重M公斤的卡車公斤的卡車;q每次可以選取某種物品的恣意多件裝載；每次可以選取某種物品的恣意多件裝載；q問選取裝載哪些物品，使得卡車運

7、送的總價值最問選取裝載哪些物品，使得卡車運送的總價值最大？大？分析q 類似多層背包問題將每個物品展開成類似多層背包問題將每個物品展開成Xi =m/wi個，然個，然后對一切的物品采用動態(tài)規(guī)劃即可。后對一切的物品采用動態(tài)規(guī)劃即可。q 假設(shè)兩件物品假設(shè)兩件物品i、j滿足滿足ci=wj,那么將物那么將物品品i去掉去掉,不用思索。這個優(yōu)化的正確性顯然：任何情況不用思索。這個優(yōu)化的正確性顯然：任何情況下都可將價值小費用高的下都可將價值小費用高的j換成物美價廉的換成物美價廉的i,得到至少不得到至少不會更差的方案。會更差的方案。q 由于每種物品有選和不選兩種情況，可以將每種物品的由于每種物品有選和不選兩種情況

8、，可以將每種物品的2k個當成一個整體思索。這樣對于某種物品要選取多個，個當成一個整體思索。這樣對于某種物品要選取多個，都可以由假設(shè)干個都可以由假設(shè)干個2k個物品進展組合個物品進展組合 (即即2進制數(shù)進制數(shù))。例。例如第如第i種物品要選種物品要選10個，那么個，那么10=23+21 。q 這樣第這樣第i種物品的個數(shù)為種物品的個數(shù)為k=2 (m/wi)物品，是一個很大物品，是一個很大的改良。的改良。q 進一步進一步, 在計算在計算k時時, K =2 (j/wi), j為當前背包剩余空間。為當前背包剩余空間。進一步for i:=1 to n do / 動態(tài)規(guī)劃，遞推求動態(tài)規(guī)劃，遞推求ffor j:=

9、m downto 1 dobeginif j=wi then /背包容量夠大背包容量夠大 fi,j:=max(fi-1,j-wi+ci,fi-1,j)else /背包容量缺乏背包容量缺乏 fi,j:=fi-1,j;end; 在這里為了使得每個物品只取在這里為了使得每個物品只取1個或不取個或不取,采用了每次取采用了每次取j都是與都是與i-1進展進展比較，實踐上保管了每比較，實踐上保管了每1步取不同步取不同j的值的值改良程序q 現(xiàn)實上，我們只關(guān)懷剩余背包的最大值，也就是僅僅關(guān)懷現(xiàn)實上，我們只關(guān)懷剩余背包的最大值，也就是僅僅關(guān)懷f(j),因此，在對因此，在對f(j)更新時，只需背包容量可以，那么可以

10、更新時，只需背包容量可以，那么可以反復(fù)更新。程序如下：反復(fù)更新。程序如下：qfor i:=1 to n do / 動態(tài)規(guī)劃，遞推求動態(tài)規(guī)劃，遞推求fqfor j:=0 to m doqbeginqif j=wi then /背包容量夠大背包容量夠大q fj:=max(fj-wi+ci,fj)qend;思索題思索題1：機器分配：機器分配 qM M臺設(shè)備，分給臺設(shè)備，分給N N個公司。個公司。q假設(shè)公司假設(shè)公司i i獲得獲得j j臺設(shè)備，那么能產(chǎn)生臺設(shè)備，那么能產(chǎn)生AijAij效益效益q問如何分配設(shè)備使得總效益最大？問如何分配設(shè)備使得總效益最大？qM=15M=15，N=10N=10。分析q用機器數(shù)

11、來做形狀，數(shù)組用機器數(shù)來做形狀，數(shù)組f(i,j)f(i,j)表示前表示前i i個公司分個公司分配配j j臺機器的最大盈利。那么形狀轉(zhuǎn)移方程為臺機器的最大盈利。那么形狀轉(zhuǎn)移方程為: :qf(i,j) =Maxfi-1f(i,j) =Maxfi-1，k + aik + ai，j-j j-j (1=i=N,1=j=M,0=k=j )(1=i=N,1=j=M,0=k=j )q初始值初始值: f(0,0)=0: f(0,0)=0q時間復(fù)雜度時間復(fù)雜度O(NO(N* *M2)M2)思索題思索題2：硬幣找零：硬幣找零l 給定給定N枚硬幣枚硬幣l 給定給定T元錢元錢l 用這用這N枚硬幣找這枚硬幣找這T元錢，使

12、得剩下的錢最少。元錢，使得剩下的錢最少。l 剩下錢數(shù)最少的找零方案中的所需的最少硬幣數(shù)。剩下錢數(shù)最少的找零方案中的所需的最少硬幣數(shù)。l N=500,T=10000.分析分析l 設(shè)設(shè)Fi表示需求找的錢數(shù)為表示需求找的錢數(shù)為i時所需求的最少錢幣時所需求的最少錢幣數(shù)。顯然有：數(shù)。顯然有：l Fi=MinF i - Aj + 1 i T，1jNl 初始值：初始值：F0=0。l Aj表示其中表示其中 第第j種錢幣的面值。種錢幣的面值。l 時間復(fù)雜度為時間復(fù)雜度為O(N*T)。思索題思索題3：系統(tǒng)可靠性：系統(tǒng)可靠性q 一個系統(tǒng)由假設(shè)干部件串聯(lián)而成，只需有一個部件缺點，一個系統(tǒng)由假設(shè)干部件串聯(lián)而成，只需有一

13、個部件缺點，系統(tǒng)就不能正常運轉(zhuǎn)，為提高系統(tǒng)的可靠性，每一部件系統(tǒng)就不能正常運轉(zhuǎn)，為提高系統(tǒng)的可靠性，每一部件都裝有備用件，一旦原部件缺點，備用件就自動進入系都裝有備用件，一旦原部件缺點，備用件就自動進入系統(tǒng)。顯然備用件越多，系統(tǒng)可靠性越高，但費用也越大，統(tǒng)。顯然備用件越多，系統(tǒng)可靠性越高，但費用也越大，那么在一定總費用限制下，系統(tǒng)的最高可靠性等于多少？那么在一定總費用限制下，系統(tǒng)的最高可靠性等于多少？q 給定一些系統(tǒng)備用件的單價給定一些系統(tǒng)備用件的單價CkCk，以及當用，以及當用MkMk個此備用件個此備用件時部件的正常任務(wù)概率時部件的正常任務(wù)概率PkPkMkMk，總費用上限，總費用上限C C。

14、求系統(tǒng)。求系統(tǒng)能夠的最高可靠性。能夠的最高可靠性。 樣例樣例輸入文件格式：輸入文件格式：第一行：第一行：n Cn C第二行：第二行：C1 P1(0) P1(1) P1(X1) C1 P1(0) P1(1) P1(X1) 0=X1=C/Ck0=X1=C/Ck 第第n n 行：行：Cn Pn(0) Pn(1) Pn(Xn) Cn Pn(0) Pn(1) Pn(Xn) 0=Xn=C/Cn0=Xn=C/Cn輸入：輸入：2 202 20 3 0.6 0.65 0.7 0.75 0.8 0.85 0.93 0.6 0.65 0.7 0.75 0.8 0.85 0.9 5 0.7 0.75 0.8 0.8

15、0.9 0.95 5 0.7 0.75 0.8 0.8 0.9 0.95輸出：輸出：0.63750.6375分析q設(shè)設(shè)f(i,j)f(i,j)表示將表示將j j的資金用到前的資金用到前i i項備用件中去的項備用件中去的最大可靠性，那么有最大可靠性，那么有q F(i,j)= F(i,j)=q maxF(i-1,jk maxF(i-1,jk* *Costi)Costi)* *Pi,kPi,kq 0=i=n, 0=j=C,0=kj div Cost(i) 0=i=n, 0=j=C,0=kj div Cost(i)q初始：初始： F(0,0)=0 F(0,0)=0q目的：目的： F(n,C) F(n,

16、C)q時間復(fù)雜度：時間復(fù)雜度：O(kO(k* *n n* *C)C)，這里，這里k k是常數(shù)因子，與數(shù)是常數(shù)因子，與數(shù)據(jù)相關(guān)據(jù)相關(guān)思索題思索題4：快餐問題：快餐問題q套餐由由套餐由由A個漢堡，個漢堡，B個薯條和個薯條和C個飲料組成個飲料組成q消費漢堡、薯條、飲料的時間為消費漢堡、薯條、飲料的時間為p1,p2,p3q有有N條流水線，條流水線，N=10，第，第i條流水線消費時間為條流水線消費時間為Tiq每條流水線都可消費漢堡、薯條和飲料每條流水線都可消費漢堡、薯條和飲料q每天漢堡、薯條和飲料個數(shù)不超越每天漢堡、薯條和飲料個數(shù)不超越100q如何安排消費使得消費套餐數(shù)量最多。如何安排消費使得消費套餐數(shù)

17、量最多。分析q對于每條流水線，它的消費時間是一定的，我們對于每條流水線，它的消費時間是一定的，我們假設(shè)知道了消費漢堡和薯條的個數(shù)，就很容易計假設(shè)知道了消費漢堡和薯條的個數(shù)，就很容易計算出消費飲料的個數(shù)。因此，算出消費飲料的個數(shù)。因此，q假設(shè)第假設(shè)第i條流水線消費了條流水線消費了i個漢堡，個漢堡，j個薯條個薯條,那么那么還能消費飲料個數(shù)為：還能消費飲料個數(shù)為：qk=(Ti-i*p1-j*p2)/p3動態(tài)規(guī)劃q 設(shè)設(shè)f(x,i,j)表示前表示前x條流水線消費條流水線消費i個漢堡，個漢堡，j個薯條最多還能消費飲料個個薯條最多還能消費飲料個數(shù)。數(shù)。q 假設(shè)前假設(shè)前x-1條流水線只需消費條流水線只需消費

18、i漢堡，漢堡，j個薯條，消費的飲料為個薯條，消費的飲料為f(x-1,i,j)q 因此有第因此有第x條流水線必需消費了條流水線必需消費了i-i個漢堡，個漢堡，j-j個薯條，剩下的時間消個薯條，剩下的時間消費費k個飲料。個飲料。q 由于前由于前x條流水線消費的飲料條流水線消費的飲料=q 前前x-1條流水線消費的飲料條流水線消費的飲料 + 第第x條流水線消費的飲料條流水線消費的飲料q 所以有，所以有，f(x,i,j)=maxf(x-1,i,j)+k32*) (1*) (ppjjpiiTxk流水線資源分配圖32*) (1*) (ppjjpiiTxk其中，思索？qf(x,i,j)=maxf(x-1,i,

19、j)+kq1=x=n=10,0=i=i=100, 0=j=j=100qk可以實時求出可以實時求出q時間復(fù)雜度為時間復(fù)雜度為10*1002*1002=109q顯然超時！顯然超時！優(yōu)化求出最多能夠消費多少套，減少不用要循環(huán)。求出最多能夠消費多少套，減少不用要循環(huán)。淘汰一些沒有意義形狀，比如消費了過多第三種淘汰一些沒有意義形狀，比如消費了過多第三種物質(zhì)，卻沒把前兩種消費滿。物質(zhì)，卻沒把前兩種消費滿。讓每條流水線大多數(shù)時間按成套時間消費，留下讓每條流水線大多數(shù)時間按成套時間消費，留下一些時間進展動態(tài)規(guī)劃，這樣將在動態(tài)規(guī)劃時，一些時間進展動態(tài)規(guī)劃，這樣將在動態(tài)規(guī)劃時，極大地減少每種物品的產(chǎn)量從而極大地減少動態(tài)極大地減少每種物品的產(chǎn)量從而極大地減少動態(tài)規(guī)劃的形狀數(shù)。規(guī)劃的形狀數(shù)。闡明q 利用前兩個優(yōu)化根本可以出解利用前兩個優(yōu)化根本可以出解q 第第3個優(yōu)化，對每條流水線進展動態(tài)規(guī)劃的剩余時間多少比較難確定，個優(yōu)化，對每條流水線進展動態(tài)規(guī)劃的剩余時間多少比較難確定，否那么正確性難以保證，剩余時間越多，正確率越高，速度越慢。以否那么正確性難以保證，剩余時間越多，正確率越高，速度越慢。以下圖是對第下圖是對第3個優(yōu)化的闡明：個優(yōu)化的闡明