第21講動態(tài)規(guī)劃背包問題

1、第21講動態(tài)規(guī)劃背包問題投資分配問題 現(xiàn)有數量為a（萬元）的資金，計劃分配給n 個工廠,用于擴大再生產。 假設：xi 為分配給第i 個工廠的資金數量（萬元）；gi(xi)為第i 個工廠得到資金后提供的利潤值（萬元）。 問題：如何確定各工廠的資金數，使得總的利潤為最大。 nixaxxgziniiniii.2.1 0)( max11據此，有下式： 令：fk(x) 表示以數量為x 的資金分配給前k 個工廠，所得到的最大利潤值。 用動態(tài)規(guī)劃求解，就是求 fn(a) 的問題。 當 k=1 時， f1(x) = g1(x) （因為只給一個工廠） 當1kn 時，其遞推關系如下： 設：y 為分給第k 個工廠的

2、資金（其中 0y x ），此時還剩 x y（萬元）的資金需要分配給前 k1 個工廠,如果采取最優(yōu)策略，則得到的最大利潤為fk1(xy) ,因此總的利潤為： gk(y) fk1(xy) 投資分配問題 nkyxfygxfkkxyk.)()(max)(3210 其中 如果a 是以萬元為資金分配單位，則式中的y 只取非負整數0，1，2，x。上式可變?yōu)椋?)()(max)(,yxfygxfkkxyk 1210所以，根據動態(tài)規(guī)劃的最優(yōu)化原理，有下式：投資分配問題設國家撥給60萬元投資，供四個工廠擴建使用，每個工廠擴建后的利潤與投資額的大小有關，投資后的利潤函數如下表所示。 投資投資利潤利潤01020304

3、05060g1(x)0205065808585g2(x)0204050556065g3(x)0256085100110115g4(x)0254050606570依據題意，是要求 f4(60) 。投資分配問題按順序解法計算。第一階段：求 f1(x)。顯然有 f1(x) g1(x)，得到下表 投資投資利潤利潤0102030405060f1(x) g1(x)0205065808585最優(yōu)策略最優(yōu)策略0102030405060第二階段：求 f2(x)。此時需考慮第一、第二個工廠如何進行投資分配，以取得最大的總利潤。 )60()(max)60(1260,10,02yfygfy 投資分配問題1200652

4、0605055655080408520850max)0()60()10()50()20()40()30()30()40()20()50()10()60()0(max12121212121212fgfgfgfgfgfgfg最優(yōu)策略為（40，20），此時最大利潤為120萬元。同理可求得其它 f2(x) 的值。 )60()(max)60(1260,10,02yfygfy 投資分配問題2210 ,10 ,50212121212121(50)m ax()(50) (0)(50)(10)(40)(20)(30) 105(30)(20)(40)(10)(50)(0)yfgyfygfgfgfgfgfgf最優(yōu)策

5、略為（最優(yōu)策略為（3030，2020），此時最大利潤為），此時最大利潤為105105萬元。萬元。投資分配問題2210 ,10 ,40(40)m ax()(40)90yfgyfy最優(yōu)策略為（20，20），此時最大利潤為90萬元。2210 ,10 ,20 ,30(30)m ax()(30)70yfgyfy最優(yōu)策略為（20，10），此時最大利潤為70萬元。投資分配問題2210 ,10 ,20(20)m ax()(20) 50yfgyfy2210,10,(10)m ax()(10)20yfgyfy最優(yōu)策略為（10，0）或（ 0 ， 10 ） ，此時最大利潤為20萬元。 f2(0) 0。最優(yōu)策略為（0，

6、0），最大利潤為0萬元。 得到下表最優(yōu)策略為（20，0），此時最大利潤為50萬元。投資分配問題 投資投資利潤利潤0102030405060f2(x)020507090105120最優(yōu)策略最優(yōu)策略(0,0)(10,0)(0,10)(20,0)(20,10)(20,20)(30,20)(40,20)第三階段：求 f3(x)。此時需考慮第一、第二及第三個工廠如何進行投資分配，以取得最大的總利潤。 )60()(max)60(2360,10,03yfygfy 投資分配問題1550115201105010070859060105251200max)0()60()10()50()20()40()30()30

7、()40()20()50()10()60()0(max23232323232323 fgfgfgfgfgfgfg最優(yōu)策略為（最優(yōu)策略為（20，10，30），最大利潤為），最大利潤為155萬元。萬元。同理可求得其它同理可求得其它 f3(x) 的值。得到下表的值。得到下表投資分配問題 投資投資利潤利潤0102030405060f3(x)0256085110135155最優(yōu)最優(yōu)策略策略(0,0,0) (0,0,10) (0,0,20) (0,0,30) (20,0,20) (20,0,30) (20,10,30)第四階段：求 f4(60)。即問題的最優(yōu)策略。)60()(max)60(3460,10,

8、04yfygfy投資分配問題16007025656060855011040135251550max)0()60()10()50()20()40()30()30()40()20()50()10()60()0(max34343434343434fgfgfgfgfgfgfg最優(yōu)策略為（20，0，30，10），最大利潤為160萬元。投資分配問題背包問題 有一個徒步旅行者，其可攜帶物品重量的限度為有一個徒步旅行者，其可攜帶物品重量的限度為a 公斤，公斤，設有設有n 種物品可供他選擇裝入包中。已知每種物品的重量及種物品可供他選擇裝入包中。已知每種物品的重量及使用價值（作用），問此人應如何選擇攜帶的物品（各

9、幾使用價值（作用），問此人應如何選擇攜帶的物品（各幾件），使所起作用（使用價值）最大？件），使所起作用（使用價值）最大？物品物品 1 2 j n重量（重量（公斤公斤/ /件件） a1 a2 aj an每件使用價值每件使用價值 c1 c2 cj cn 這就是背包問題。類似的還有工廠里的下料問題、運輸中的貨物裝載問題、人造衛(wèi)星內的物品裝載問題等。 從每種物品的角度考慮，與它相關的策略從每種物品的角度考慮，與它相關的策略已并非取或不取已并非取或不取 兩種，而是有取兩種，而是有取0件、取件、取1件、取件、取2件件等很多種。如果仍然按照解等很多種。如果仍然按照解01背包時的思路，令背包時的思路，令fiv

10、表示前表示前i種物品種物品恰放入一個容量為恰放入一個容量為v的背包的最大權的背包的最大權 值。仍值。仍然可以按照每種物品不同的策略寫出狀態(tài)然可以按照每種物品不同的策略寫出狀態(tài)轉移方程，像這樣：轉移方程，像這樣：fiv=maxfi-1v-k*ci+k*wi|0=k*ci=wi 1=i=wi then m:=f(x-i)+ci;16 if mt then t:=m;17 end;18 f:=t;19 end;20end;2122begin23readln(m,n);24for i:= 1 to n do25 readln(wi,ci);26writeln(f(m);27end. 當當m不大時不大時

11、,可以通過可以通過,但當但當m較大時較大時,容易超容易超時，改進的遞歸法時，改進的遞歸法 改進的的遞歸法的思想還是以空間換時間改進的的遞歸法的思想還是以空間換時間,這只要將遞歸函數計算過程中的各個子函這只要將遞歸函數計算過程中的各個子函數的值保存起來數的值保存起來,開辟一個一維數組即可開辟一個一維數組即可 其實這種以空間換時間的存儲式搜索就是其實這種以空間換時間的存儲式搜索就是動態(tài)規(guī)劃的思想動態(tài)規(guī)劃的思想 1program knapsack04; 2const maxm=2000;maxn=30; 3type ar=array0.maxn of integer; 4var m,n,j,i,t:

12、integer; 5 c,w:ar; 6 p:array0.maxm of integer; 7function f(x:integer):integer; 8var i,t,m:integer; 9begin10 if px-1 then f:=px /標記是標記是否計算過避免重復計算（很重要）否計算過避免重復計算（很重要）11 else 12 begin114 begin15 t:=-1;16 for i:=1 to n do 3 v17 begin18 if x=wi then m:=f(i-wi)+ci;19 if mt then t:=m;20 end;21 px:=t;22 end

13、;23 f:=px;24 end;25end;2627begin28 readln(m,n);29 for i:= 1 to n do30 readln(wi,ci);31 fillchar(p,sizeof(p),-1); /搜索中用于存儲各階段的最優(yōu)質32 writeln(f(m);33end.0-1背包問題給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為C。問應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?niiixv1maxnixCxwiniii1,1 , 010-1背包問題0-1背包問題是一個特殊的整數規(guī)劃問題。 有N件物品和一個容量為V的背包。第i件物

14、品的費用是ci，價值是wi。求解將哪些物品裝入背包可使價值總和最大。 這是最基礎的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。用子問題定義狀態(tài)：即用子問題定義狀態(tài)：即fiv表示前表示前i件物品恰放入件物品恰放入(不一定真的是每個不一定真的是每個都放進去，而是指最有策略）一個容量為都放進去，而是指最有策略）一個容量為v的背包可以獲得的最大價的背包可以獲得的最大價值。則其狀態(tài)轉移方程便是：值。則其狀態(tài)轉移方程便是：fiv=maxfi-1v,fi-1v-ci+wi這個方程非常重要，基本上所有跟背包相關的問題的方程都是由它衍這個方程非常重要，基本上所有跟背包相關的問題的方程都是由它衍生出來的

15、。所以有必要將它詳細解釋一下：生出來的。所以有必要將它詳細解釋一下： “將前i件物品放入容量為v的背包中”這個子問題 若只考慮第i件物品的策略（放或不放），那么就可以轉化為一個只牽扯前i-1件物品的問題。 如果不放第i件物品，那么問題就轉化為“前i-1件物品放入容量為v的背包中”，價值為fi-1v； 如果放第i件物品，那么問題就轉化為“前i-1件物品放入剩下的容量為v-ci的背包中”，此時能獲得的最大價值就是fi-1v-ci再加上通過放入第i件物品獲得的價值wi。 這個問題非常類似于這個問題非常類似于01背包問題，所不同背包問題，所不同的是每種物品有無限件。也就是從每種物的是每種物品有無限件。

16、也就是從每種物品的角度考慮，與它相關的策略已并非取品的角度考慮，與它相關的策略已并非取或不取或不取 兩種，而是有取兩種，而是有取0件、取件、取1件、取件、取2件件等很多種。如果仍然按照解等很多種。如果仍然按照解01背包背包時的思路，令時的思路，令fiv表示前表示前i種物品恰放入一種物品恰放入一個容量為個容量為v的背包的最大權的背包的最大權 值。仍然可以按值。仍然可以按照每種物品不同的策略寫出狀態(tài)轉移方程，照每種物品不同的策略寫出狀態(tài)轉移方程，像這樣：像這樣：fiv=maxfi-1v-k*ci+k*wi|0=k*ci2n時，算法需要(n2n)計算時間。 0-1背包問題01背包問題描述：一個旅行者

17、有一個最多能用M公斤的背包，現(xiàn)在有N件物品，它們的重量分別是W1，W2，.,Wn,它們的價值分別為P1,P2,.,Pn.若每種物品只有一件求旅行者能獲得最大總價值。方式一：遍歷M*N的數組，對應下圖包的總容量M20,物品種類數N5代碼如下：代碼如下：const int nRes=5;/5種物品種物品int nResWeightnRes+1=0,5,3,4,7,8;/每種物品對應重量每種物品對應重量int nResValuenRes+1=0,14,6,9,18,20;/每種物品對應價值每種物品對應價值const int nTotleW=20;/背包容量為背包容量為20int nValueTabl

18、enRes+1nTotleW+1=0;/動態(tài)價值表，每一項對應包當前所能裝入的最優(yōu)值動態(tài)價值表，每一項對應包當前所能裝入的最優(yōu)值int KitBag()for(int i=1;i=nRes;i+)for(int j=1;j=nResWeighti) /當包容量大于等于當前物品重時當包容量大于等于當前物品重時/如果裝入當前物品所能達最大價值如果裝入當前物品所能達最大價值不裝當前物品，包選裝前面物品所能獲得的最大價值不裝當前物品，包選裝前面物品所能獲得的最大價值/裝入當前物品所能達最大價值裝入當前物品所能達最大價值=當前物品價值當前物品價值+當前包容量當前包容量j扣除當前物品重量后，剩余的容量所能

19、裝入的最大價值?？鄢斍拔锲分亓亢?，剩余的容量所能裝入的最大價值。/對照上表，當遍歷到對照上表，當遍歷到i=2,j=8時，時，nValueTablei-1j-nResWeighti=nValueTable15=14，滿足條件就裝入物品。，滿足條件就裝入物品。 if(nResValuei+nValueTablei-1j-nResWeightinValueTablei-1j)nValueTableij=nResValuei+nValueTablei-1j-nResWeighti;/當前物品裝入包當前物品裝入包. else/當前物品不裝入包，當前包容量下的最大價值仍然是原來的價值當前物品不裝入包，當

20、前包容量下的最大價值仍然是原來的價值nValueTableij=nValueTablei-1j;else/包容量不足以裝入當前物品時，沿用原來的包容量最大價值包容量不足以裝入當前物品時，沿用原來的包容量最大價值nValueTableij=nValueTablei-1j; cout最大值為：最大值為：=nResWeightnR)/包容量大于等于當前物品重包容量大于等于當前物品重/獲得物品放入和不放入兩種情況中的價值最大者獲得物品放入和不放入兩種情況中的價值最大者nValueTablenRnW=max(nResValuenR+RecursionBag(nR-1,nW-nResWeightnR),/

21、物品入包后的價值物品入包后的價值RecursionBag(nR-1,nW);/物品不入包的最大價值物品不入包的最大價值else/包容量不足以放入當前物品包容量不足以放入當前物品nValueTablenRnW=RecursionBag(nR-1,nW);return nValueTablenRnW; 對比兩種方式可知，第二種方式遍歷的數據對比兩種方式可知，第二種方式遍歷的數據量為黃色標注結點，要小于第一種方式的數量為黃色標注結點，要小于第一種方式的數據訪問量。據訪問量。 0-1背包問題基本題型：二維背包問題上面討論的背包問題只有一種限制，即旅行者所能承受的背包的重量（亦即重量不能超過akg）.但

22、是實際上背包除受重量的限制外，還有體積的限制，這就是不但要求旅行者的背包的重量M不能超過a（kg），還要求旅行者背包的體積V不能超過b（m3）,我們把這樣的問題稱為“二維背包問題”。所謂“二維”是指在用動態(tài)規(guī)劃處理時，它的狀態(tài)變量有兩個因素:一個是重量，一個是體積。 二維費用的背包問題二維背包問題的條件可概括為下表 物品編號物品編號 12j n1 n單位重量（單位重量（kg） a1 a2 aj an-1 an 單位體積（單位體積（m3） b1 b2 bj bn-1 bn 單位價值單位價值 c1 c2 cj cn-1 cn 二維費用的背包問題二維背包問題可以歸納為如下形式的整數線性規(guī)劃問題： m

23、axc1x1+cixi+cnxn a1x1+aixi+anxna b1x1+bixi+bnxnb xi為非負整數，i=1，n正如一維背包問題那樣，二維背包問題也可以用動態(tài)規(guī)劃求解。 二維費用的背包問題二維費用的背包問題 問題問題 二維費用的背包問題是指：對于每件物品，二維費用的背包問題是指：對于每件物品，具有兩種不同的費用；選擇這件物品必須具有兩種不同的費用；選擇這件物品必須同時付出這兩種代價；對于每種代價都有同時付出這兩種代價；對于每種代價都有一個可付出的最大值（背包容量）。問怎一個可付出的最大值（背包容量）。問怎樣選擇物品可以得到最大的價值。設這兩樣選擇物品可以得到最大的價值。設這兩種代價

24、分別為代價種代價分別為代價1和代價和代價2，第，第i件物品所件物品所需的兩種代價分別為需的兩種代價分別為ai和和bi。兩種代價。兩種代價可付出的最大值（兩種背包容量）分別為可付出的最大值（兩種背包容量）分別為V和和U。物品的價值為。物品的價值為wi。算法思想 費用加了一維，只需狀態(tài)也加一維即可。費用加了一維，只需狀態(tài)也加一維即可。設設fivu表示前表示前i件物品付出兩種代價分件物品付出兩種代價分別為別為v和和u時可獲得的最大價值。狀態(tài)轉移時可獲得的最大價值。狀態(tài)轉移方程就是：方程就是： fivu=maxfi-1vu,fi-1v-aiu-bi+wi。碼頭有一艘載重量為30t，最大容為1210m3

25、的船，由于運輸需要,這艘船可用于裝載四種貨物到珠江口，它們的單位體積,重量及價值量見下表:體積（體積（10m10m3 3） 重量（重量（t t） 價值量價值量 A 2 5 2B 6 4 2C 3 6 3D 4 7 4現(xiàn)求如何裝載這四種貨物使價值量最大。 背包問題小結（1） 一、01背包 最簡單的背包，每件物品選或者不選。for(int i = 1; i = ci; -j) dpj = max(dpj,dpj-ci+ai); 二、完全背包 每件物品可以選無限次for(int i = 1; i = n; +i) for(int j = ci; j = V; +j) dpj = max(dpj,dp

26、j-ci + ai; 注意：初始化方面的細節(jié)，如果要求恰好裝滿背包，那么在初始化時除了dp0為0其它dp1.V均設為-（求的是最大解，如果求的是最小解，則為） 如果并沒有要求必須把背包裝滿，而是只希望價格盡量大，初始化時應該將f0.V全部設為0。 三、多重背包 每件物品可以選有限次 設每件物品的個數為counti; O(V*log counti)寫法（二進制優(yōu)化）for(int i = 1; i = n; +i) int k; for(k = 1; k*2 = k*ci ; -j) dpj = max(dpj,dpj-k*ci + k*ai); k = counti + 1 - k; for(

27、int j = V; j = k*ci; -j) dpj = max(dpj,dpj-k*ci + k*ai); O(VN)的寫法 /*此種方法求最大值不確定可否，但判斷是否能將1-V內的背包裝滿可以*/int usedMAXN;for(int i = 1; i = N; +i) memset(used,0,sizeof(used); for(int j = ci; j = V; +j) if(usedj-ci counti & dpj dpj-ci + ai) dpj = dpj-ci + ai; usedj = usedj-ci + 1; /有待驗證，估計不對，有興趣的可以驗證下現(xiàn)

28、在dpi用來表示容量為i的背包能否被所給物品恰好裝滿 上面的01背包和完全背包以及上面一種O(V*log counti)的寫法也可以做這樣的改變memset(dp,false,sizeof(dp);dp0 = true;for(int i = 1; i = N; +i) memset(used,0,sizeof(used); for(int j = ci; j = V; +j) /注意這里是順序的（和完全背包相同），其實多重背包也可以理解成被限制了的完全背包 if(!dpj & dpj-ci & usedj-ci counti) /注意這里的!dpj不能少 dpj = true; usedj = usedj-ci + 1; 四、混合背包 以上三種背包的混合，有的物品只能取一次，有的物品能取無限次，有的物品能取有限次算法偽代碼：for i=1.n if 第i件物品是0