第9章第3節(jié) 動態(tài)規(guī)劃背包問題(C++版)

1、第九章第九章 動態(tài)規(guī)劃動態(tài)規(guī)劃第三節(jié)第三節(jié) 背包問題背包問題第三節(jié)第三節(jié) 背包問題背包問題一、一、01背包問題背包問題問題：問題： 有有N件物品和一個容量為件物品和一個容量為V的背包。第的背包。第i件物品的費用（即體積，下同）是件物品的費用（即體積，下同）是wi，價值是價值是ci。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。且價值總和最大。 基本思路：基本思路：這是最基礎的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。這是最基礎的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。用子問題定

2、義狀態(tài)：即用子問題定義狀態(tài)：即fiv表示前表示前i件物品件物品(部分或全部部分或全部)恰放入一個容量為恰放入一個容量為v的背包可以獲得的最大價值。則其狀態(tài)轉(zhuǎn)移方程便是：的背包可以獲得的最大價值。則其狀態(tài)轉(zhuǎn)移方程便是：fiv=maxfi-1v,fi-1v-wi+ci。這個方程非常重要，基本上所有跟背包相關(guān)的問題的方程都是由它衍生出來這個方程非常重要，基本上所有跟背包相關(guān)的問題的方程都是由它衍生出來的。所以有必要將它詳細解釋一下：的。所以有必要將它詳細解釋一下：“將前將前i件物品放入容量為件物品放入容量為v的背包中的背包中”這個這個子問題，若只考慮第子問題，若只考慮第i件物品的策略（放或不放），那

3、么就可以轉(zhuǎn)化為一個只牽扯件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個只牽扯前前i-1件物品的問題。如果不放第件物品的問題。如果不放第i件物品，那么問題就轉(zhuǎn)化為件物品，那么問題就轉(zhuǎn)化為“前前i-1件物品放入容件物品放入容量為量為v的背包中的背包中”；如果放第；如果放第i件物品，那么問題就轉(zhuǎn)化為件物品，那么問題就轉(zhuǎn)化為“前前i-1件物品放入剩下件物品放入剩下的容量為的容量為v-wi的背包中的背包中”，此時能獲得的最大價值就是，此時能獲得的最大價值就是f i-1v-wi再加上通過再加上通過放入第放入第i件物品獲得的價值件物品獲得的價值ci。 注意注意fiv有意義當且僅當存在一個前有意義當且僅當存在

4、一個前i件物品的子集，其費用總和為件物品的子集，其費用總和為v。所。所以按照這個方程遞推完畢后，最終的答案并不一定是以按照這個方程遞推完畢后，最終的答案并不一定是fNV，而是，而是fN0.V的的最大值。如果將狀態(tài)的定義中的最大值。如果將狀態(tài)的定義中的“恰恰”字去掉，在轉(zhuǎn)移方程中就要再加入一項字去掉，在轉(zhuǎn)移方程中就要再加入一項fi-1v，這樣就可以保證，這樣就可以保證fNV就是最后的答案。但是若將所有就是最后的答案。但是若將所有fij的初始值的初始值都賦為都賦為0，你會發(fā)現(xiàn)，你會發(fā)現(xiàn)fnv也會是最后的答案。為什么呢？因為這樣你默認了最也會是最后的答案。為什么呢？因為這樣你默認了最開始開始fij是

5、有意義的，只是價值為是有意義的，只是價值為0，就看作是無物品放的背包價值都為，就看作是無物品放的背包價值都為0，所，所以對最終價值無影響，這樣初始化后的狀態(tài)表示就可以把以對最終價值無影響，這樣初始化后的狀態(tài)表示就可以把“恰恰”字去掉。字去掉。w優(yōu)化空間復雜度優(yōu)化空間復雜度 w 以上方法的時間和空間復雜度均為O(N*V)，其中時間復雜度基本已經(jīng)不能再優(yōu)化了，但空間復雜度卻可以優(yōu)化到O(V)。w先考慮上面講的基本思路如何實現(xiàn)，肯定是有一個主循環(huán)i=1.N，每次算出來二維數(shù)組fi0.V的所有值。那么，如果只用一個數(shù)組f 0.V，能不能保證第i次循環(huán)結(jié)束后fv中表示的就是我們定義的狀態(tài)fiv呢？fiv

6、是由fi-1v和fi-1v-wi兩個子問題遞推而來，能否保證在推fiv時（也即在第i次主循環(huán)中推fv時）能夠得到fi-1v和fi-1v-wi的值呢？事實上，這要求在每次主循環(huán)中我們以v=V.0的逆序推fv，這樣才能保證推fv時fv-wi保存的是狀態(tài)fi-1v-wi的值。w偽代碼如下：wfor i=1.N wfor v=V.0 wfv=maxfv,fv-wi+ci; w其中fv=maxfv,fv-wi+ci相當于轉(zhuǎn)移方程fiv=maxfi-1v,fi-1v-wi+ci，因為現(xiàn)在的fv-wi就相當于原來的fi-1v-wi。如果將v的循環(huán)順序從上面的逆序改成順序的話，那么則成了fiv由fiv-wi推

7、知，與本題意不符，但它卻是另一個重要的完全背包問題最簡捷的解決方案，故學習只用一維數(shù)組解01背包問題是十分必要的。 【例例1】 0/1背包背包【問題描述】 一個旅行者有一個最多能用m公斤的背包，現(xiàn)在有n件物品，它們的重量分別是W1，W2，.,Wn,它們的價值分別為C1,C2,.,Cn.若每種物品只有一件求旅行者能獲得最大總價值。 【輸入格式】w 第一行：兩個整數(shù)，M(背包容量，M=200)和N(物品數(shù)量，N=30)；w 第2.N+1行：每行二個整數(shù)Wi,Ci，表示每個物品的重量和價值。【輸出格式】w 僅一行，一個數(shù)，表示最大總價值。【樣例輸入】package.inw10 4w2 1w3 3w4

8、 5w7 9【樣例輸出】package.outw12【解法一】設fiv表示前i件物品，總重量不超過v的最優(yōu)價值，則fiv=max(fi-1v-wi+ci，fi-1v) ；fnm即為最優(yōu)解,給出程序：#includeusing namespace std;const int maxm = 201, maxn = 31;int m, n;int wmaxn, cmaxn;int fmaxnmaxm; int max(int x,int y) xy?x:y; /求x和y最大值int main() scanf(%d%d,&m, &n); /背包容量m和物品數(shù)量n for (int i

9、= 1; i = n; i+) /在初始化循環(huán)變量部分，定義一個變量并初始化 scanf(%d%d,&wi,&ci); /每個物品的重量和價值 for (int i = 1; i 0; v-) if (wi =wi，1=i=n 。程序如下：#includeusing namespace std;const int maxm = 2001, maxn = 31;int m, n;int wmaxn, cmaxn;int fmaxm; int main() scanf(%d%d,&m, &n); /背包容量m和物品數(shù)量n for (int i=1; i = n; i

10、+) scanf(%d%d,&wi,&ci); /每個物品的重量和價值 for (int i=1; i = wi; v-) if (fv-wi+cifv) fv = fv-wi+ci;printf(%d,fm); / f(m)為最優(yōu)解return 0; 總結(jié):01背包問題是最基本的背包問題，它包含了背包問題中設計狀態(tài)、方程的最基本思想，另外，別的類型的背包問題往往也可以轉(zhuǎn)換成01背包問題求解。故一定要仔細體會上面基本思路的得出方法，狀態(tài)轉(zhuǎn)移方程的意義，以及最后怎樣優(yōu)化的空間復雜度。 二、完全背包問題問題:有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的費用是

11、wi，價值是ci。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。 基本思路:這個問題非常類似于01背包問題，所不同的是每種物品有無限件。也就是從每種物品的角度考慮，與它相關(guān)的策略已并非取或不取兩種，而是有取0件、取1件、取2件等很多種。如果仍然按照解01背包時的思路，令fiv表示前i種物品恰放入一個容量為v的背包的最大權(quán)值。仍然可以按照每種物品不同的策略寫出狀態(tài)轉(zhuǎn)移方程，像這樣：fiv=maxfi-1v-k*wi+k*ci|0=k*wi= v。將01背包問題的基本思路加以改進，得到了這樣一個清晰的方法。這說明01背包問題的方程的確是很重要，可以推及其它類型的背包問

12、題。這個算法使用一維數(shù)組，先看偽代碼：for i=1.N for v=0.V fv=maxfv,fv-wi+ci; 你會發(fā)現(xiàn)，這個偽代碼與01背包問題的偽代碼只有v的循環(huán)次序不同而已。為什么這樣一改就可行呢？首先想想為什么01背包問題中要按照v=V.0的逆序來循環(huán)。這是因為要保證第i次循環(huán)中的狀態(tài)fiv是由狀態(tài)fi-1v-wi遞推而來。換句話說，這正是為了保證每件物品只選一次，保證在考慮“選入第i件物品”這件策略時，依據(jù)的是一個絕無已經(jīng)選入第i件物品的子結(jié)果fi-1v-wi。而現(xiàn)在完全背包的特點恰是每種物品可選無限件，所以在考慮“加選一件第i種物品”這種策略時，卻正需要一個可能已選入第i種物品

13、的子結(jié)果fiv-wi，所以就可以并且必須采用v= 0.V的順序循環(huán)。這就是這個簡單的程序為何成立的道理。這個算法也可以以另外的思路得出。例如，基本思路中的狀態(tài)轉(zhuǎn)移方程可以等價地變形成這種形式：fiv=maxfi-1v,fiv-wi+ci，將這個方程用一維數(shù)組實現(xiàn)，便得到了上面的偽代碼。 【例9-12】、完全背包問題【問題描述】設有n種物品，每種物品有一個重量及一個價值。但每種物品的數(shù)量是無限的，同時有一個背包，最大載重量為M，今從n種物品中選取若干件(同一種物品可以多次選取)，使其重量的和小于等于M，而價值的和為最大。【輸入格式】第一行：兩個整數(shù)，M(背包容量，M=200)和N(物品數(shù)量，N=

14、30)；第2.N+1行：每行二個整數(shù)Wi,Ci，表示每個物品的重量和價值?！据敵龈袷健?僅一行，一個數(shù)，表示最大總價值。【樣例輸入】knapsack.in 10 4 2 1 3 3 4 5 7 9【樣例輸出】knapsack.out max=12【解法一】設fiv表示前i件物品，總重量不超過v的最優(yōu)價值，則fiv=max(fiv-wi+ci，fi-1v) ；fnm即為最優(yōu)解?！緟⒖汲绦颉?includeusing namespace std;const int maxm = 201, maxn = 31;int m, n;int wmaxn, cmaxn;int fmaxnmaxm; int

15、main() scanf(%d%d,&m, &n); /背包容量m和物品數(shù)量n for (int i = 1; i = n; i+) scanf(“%d%d”,&wi,&ci); /每個物品的重量和價值 for (int i = 1; i = n; i+) /fiv表示前i件物品，總重量不超過v的最優(yōu)價值 for (int v = 1; v = m; v+) if (v fiv-wi+ci) fiv = fi-1v; else fiv = fiv-wi+ci; printf(max=%d,fnm); / fnm為最優(yōu)解 return 0;【解法二】解法二】本問題

16、的數(shù)學模型如下：本問題的數(shù)學模型如下： 設設 f(v)表示重量不超過表示重量不超過v公斤的最大價值，公斤的最大價值， 則則 f(v)=maxf(v)，f(v-wi)+ci （v=wi ，1=i=n） ?！緟⒖汲绦颉俊緟⒖汲绦颉?includeusing namespace std;const int maxm=2001,maxn=31;int n,m,v,i;int cmaxn,wmaxn;int fmaxm;int main() scanf(%d%d,&m,&n); /背包容量背包容量m和物品數(shù)量和物品數(shù)量n for(i=1;i=n;i+) scanf(%d%d,&w

17、i,&ci); for(i=1;i=n;i+) for(v=wi;vfv) fv=fv-wi+ci; printf(max=%dn,fm); / fm為最優(yōu)解為最優(yōu)解 return 0;一個簡單有效的優(yōu)化 完全背包問題有一個很簡單有效的優(yōu)化，是這樣的：若兩件物品i、j滿足wi=cj，則將物品j去掉，不用考慮。這個優(yōu)化的正確性顯然：任何情況下都可將價值小費用高的j換成物美價廉的i，得到至少不會更差的方案。對于隨機生成的數(shù)據(jù)，這個方法往往會大大減少物品的件數(shù)，從而加快速度。然而這個并不能改善最壞情況的復雜度，因為有可能特別設計的數(shù)據(jù)可以一件物品也去不掉。轉(zhuǎn)化為01背包問題求解 既然01背包

18、問題是最基本的背包問題，那么我們可以考慮把完全背包問題轉(zhuǎn)化為01背包問題來解。最簡單的想法是，考慮到第i種物品最多選V/wi件，于是可以把第i種物品轉(zhuǎn)化為V/wi件費用及價值均不變的物品，然后求解這個01背包問題。這樣完全沒有改進基本思路的時間復雜度，但這畢竟給了我們將完全背包問題轉(zhuǎn)化為01背包問題的思路：將一種物品拆成多件物品。更高效的轉(zhuǎn)化方法是：把第i種物品拆成費用為wi*2k、價值為ci*2k的若干件物品，其中k滿足wi*2kV。這是二進制的思想，因為不管最優(yōu)策略選幾件第i種物品，總可以表示成若干個2k件物品的和。這樣把每種物品拆成O(log(V/wi)+1)件物品，是一個很大的改進?？?/p>

19、結(jié) 完全背包問題也是一個相當基礎的背包問題，它有兩個狀態(tài)轉(zhuǎn)移方程，分別在“基本思路”以及“O(VN)的算法“的小節(jié)中給出。希望你能夠?qū)@兩個狀態(tài)轉(zhuǎn)移方程都仔細地體會，不僅記住，也要弄明白它們是怎么得出來的，最好能夠自己想一種得到這些方程的方法。事實上，對每一道動態(tài)規(guī)劃題目都思考其方程的意義以及如何得來，是加深對動態(tài)規(guī)劃的理解、提高動態(tài)規(guī)劃功力的好方法。三、多重背包問題有N種物品和一個容量為V的背包。第i種物品最多有ni件可用，每件費用是wi，價值是ci。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。 基本算法: 這題目和完全背包問題很類似。基本的方程只需將完全背包

20、問題的方程略微一改即可，因為對于第i種物品有ni+1種策略：取0件，取1件取ni件。令fiv表示前i種物品恰放入一個容量為v的背包的最大權(quán)值，則：fiv=maxfi-1v-k*wi+ k*ci|0=k0的最大整數(shù)(注意：這些系數(shù)已經(jīng)可以組合出1ni內(nèi)的所有數(shù)字)。例如，如果ni為13，就將這種物品分成系數(shù)分別為1,2,4,6的四件物品。 分成的這幾件物品的系數(shù)和為ni，表明不可能取多于ni件的第i種物品。另外這種方法也能保證對于0.ni間的每一個整數(shù)，均可以用若干個系數(shù)的和表示，這個證明可以分0.2k-1和2k.ni兩段來分別討論得出，并不難，希望你自己思考嘗試一下。 這樣就將第i種物品分成了

21、O(logni)種物品，將原問題轉(zhuǎn)化為了復雜度為O(V*logni)的01背包問題，是很大的改進。【例例3】慶功會慶功會【問題描述問題描述】w為了慶賀班級在校運動會上取得全校第一名成績，班主任決定開一場慶功會，為此撥款購買獎品犒勞運動員。期望撥款金額能購買最大價值的獎品，可以補充他們的精力和體力?！据斎敫袷捷斎敫袷健縲第一行二個數(shù)n(n=500)，m(m=6000)，其中n代表希望購買的獎品的種數(shù)，m表示撥款金額。w接下來n行，每行3個數(shù)，v、w、s，分別表示第I種獎品的價格、價值（價格與價值是不同的概念）和購買的數(shù)量（買買0件到件到s件均可件均可），其中v=100，w=1000，s=10?！?/p>

22、輸出格式輸出格式】w第一行：一個數(shù)，表示此次購買能獲得的最大的價值（注意！不是價格）?！据斎霕永斎霕永縲5 1000w80 20 4w40 50 9w30 50 7w40 30 6w20 20 1【輸出樣例輸出樣例】w1040【解法一】樸素算法 【參考程序】#includeusing namespace std;int v6002, w6002, s6002;int f6002;int n, m;int max(int x,int y) if (x y) return y; else return x; int main() scanf(%d%d,&n,&m); for (

23、int i = 1; i = n; i+) scanf(%d%d%d,&vi,&wi,&si); for (int i = 1; i = 0; j-) for (int k = 0; k = si; k+) if (j-k*vi0) break; fj = max(fj,fj-k*vi+k*wi); printf(%d,fm); return 0; 【解法二】進行二進制優(yōu)化，轉(zhuǎn)換為01背包【參考程序】#includeint v10001,w10001;int f6001;int n,m,n1;int max(int a,int b) return ab?a:b; /這句

24、話等于：if (ab) return a; else return b;int main() scanf(%d%d,&n,&m); for(int i=1;i=t) v+n1=x*t; /相當于n1+; vn1=x*t; wn1=y*t; s-=t; t*=2; v+n1=x*s; wn1=y*s; /把s以2的指數(shù)分堆：1，2，4，2(k-1)，s-2k+1, for(int i=1;i=vi;j-) fj=max(fj,fj-vi+wi); printf(%dn,fm); return 0;小結(jié) 這里我們看到了將一個算法的復雜度由O(V*ni)改進到O(V*logni)的過

25、程，還知道了存在應用超出NOIP范圍的知識的O(VN)算法。希望你特別注意“拆分物品”的思想和方法，自己證明一下它的正確性，并用盡量簡潔的程序來實現(xiàn)。 四、混合三種背包問題問題如果將01背包、完全背包、多重背包混合起來。也就是說，有的物品只可以取一次（01背包），有的物品可以取無限次（完全背包），有的物品可以取的次數(shù)有一個上限（多重背包）。應該怎么求解呢？ 01背包與完全背包的混合考慮到在01背包和完全背包中最后給出的偽代碼只有一處不同，故如果只有兩類物品：一類物品只能取一次，另一類物品可以取無限次，那么只需在對每個物品應用轉(zhuǎn)移方程時，根據(jù)物品的類別選用順序或逆序的循環(huán)即可，復雜度是O(VN)

26、。偽代碼如下：for i=1.N if 第i件物品是01背包 for v=V.0 fv=maxfv,fv-wi+ci; else if 第i件物品是完全背包 for v=0.V fv=maxfv,fv-wi+ci; 再加上多重背包 如果再加上有的物品最多可以取有限次，那么原則上也可以給出O(VN)的解法：遇到多重背包類型的物品用單調(diào)隊列解即可。但如果不考慮超過NOIP范圍的算法的話，用多重背包中將每個這類物品分成O(log ni)個01背包的物品的方法也已經(jīng)很優(yōu)了?！纠纠?】混合背包混合背包【問題描述問題描述】w一個旅行者有一個最多能用V公斤的背包，現(xiàn)在有n件物品，它們的重量分別是W1，W2

27、，.,Wn，它們的價值分別為C1,C2,.,Cn。有的物品只可以取一次（01背包），有的物品可以取無限次（完全背包），有的物品可以取的次數(shù)有一個上限（多重背包）。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大?！据斎敫袷捷斎敫袷健縲第一行：二個整數(shù)，V(背包容量，V=200)，N(物品數(shù)量，N=30)；w第2.N+1行：每行三個整數(shù)Wi,Ci,Pi，前兩個整數(shù)分別表示每個物品的重量，價值，第三個整數(shù)若為0，則說明此物品可以購買無數(shù)件，若為其他數(shù)字，則為此物品可購買的最多件數(shù)(Pi)?！据敵龈袷健俊据敵龈袷健縲僅一行，一個數(shù)，表示最大總價值。【樣例輸入】【樣例輸入】m

28、ix.inw10 4w2 1 0w3 3 1w4 5 4【樣例輸出】【樣例輸出】mix.outw11【樣例解釋樣例解釋】w選第一件物品1件和第三件物品2件。 【參考程序】【參考程序】#includeusing namespace std;int m, n;int w31, c31, p31;int f201;int max(int x,int y) return xy?x:y; int main() scanf(%d%d,&m,&n); for (int i = 1; i = n; i+) scanf(%d%d%d,&wi,&ci,&pi); for (

29、int i = 1; i = n; i+) if (pi = 0) /完全背包 for (int j = wi; j = m; j+) fj = max(fj, fj-wi+ci); else for (int j = 1; j = wi; k-) fk = max(fk,fk-wi+ci); printf(%d,fm); return 0; w小結(jié) w有人說，困難的題目都是由簡單的題目疊加而來的。這句話是否是公理暫且存之不論，但它在本講中已經(jīng)得到了充分的體現(xiàn)。本來01背包、完全背包、多重背包都不是什么難題，但將它們簡單地組合起來以后就得到了這樣一道一定能嚇倒不少人的題目。但只要基礎扎實，領會

30、三種基本背包問題的思想，就可以做到把困難的題目拆分成簡單的題目來解決。w五、二維費用的背包問題五、二維費用的背包問題w問題問題w二維費用的背包問題是指：對于每件物品，具有兩種不同的費用；選擇這二維費用的背包問題是指：對于每件物品，具有兩種不同的費用；選擇這件物品必須同時付出這兩種代價；對于每種代價都有一個可付出的最大值（背包件物品必須同時付出這兩種代價；對于每種代價都有一個可付出的最大值（背包容量）。問怎樣選擇物品可以得到最大的價值。設這兩種代價分別為代價容量）。問怎樣選擇物品可以得到最大的價值。設這兩種代價分別為代價1和代和代價價2，第，第i件物品所需的兩種代價分別為件物品所需的兩種代價分別

31、為ai和和bi。兩種代價可付出的最大值（兩。兩種代價可付出的最大值（兩種背包容量）分別為種背包容量）分別為V和和U。物品的價值為。物品的價值為ci。w算法算法w費用加了一維，只需狀態(tài)也加一維即可。設費用加了一維，只需狀態(tài)也加一維即可。設fivu表示前表示前i件物品付出兩種件物品付出兩種代價分別為代價分別為v和和u時可獲得的最大價值。時可獲得的最大價值。w狀態(tài)轉(zhuǎn)移方程就是：狀態(tài)轉(zhuǎn)移方程就是：f ivu=maxfi-1vu,fi-1v-aiu-bi+ci。如前述方法，可以只使用二維的數(shù)組：當每件物品只可以取一次時變量如前述方法，可以只使用二維的數(shù)組：當每件物品只可以取一次時變量v和和u采用采用逆序

32、的循環(huán)，當物品有如完全背包問題時采用順序的循環(huán)。當物品有如多重背包逆序的循環(huán)，當物品有如完全背包問題時采用順序的循環(huán)。當物品有如多重背包問題時拆分物品。問題時拆分物品。w物品總個數(shù)的限制物品總個數(shù)的限制 w有時，有時，“二維費用二維費用”的條件是以這樣一種隱含的方式給出的：最多只能取的條件是以這樣一種隱含的方式給出的：最多只能取M件物品。這事實上相當于每件物品多了一種件物品。這事實上相當于每件物品多了一種“件數(shù)件數(shù)”的費用，每個物品的件數(shù)費的費用，每個物品的件數(shù)費用均為用均為1，可以付出的最大件數(shù)費用為，可以付出的最大件數(shù)費用為M。換句話說，設。換句話說，設fvm表示付出費用表示付出費用v、最

33、多選最多選m件時可得到的最大價值，則根據(jù)物品的類型（件時可得到的最大價值，則根據(jù)物品的類型（01、完全、多重）用不同、完全、多重）用不同的方法循環(huán)更新，最后在的方法循環(huán)更新，最后在f0.V0.M范圍內(nèi)尋找答案。范圍內(nèi)尋找答案。w另外，如果要求另外，如果要求“恰取恰取M件物品件物品”，則在，則在f0.VM范圍內(nèi)尋找答案。范圍內(nèi)尋找答案?！纠?】潛水員潛水員【問題描述問題描述】w 潛水員為了潛水要使用特殊的裝備。他有一個帶2種氣體的氣缸：一個為氧氣，一個為氮氣。讓潛水員下潛的深度需要各種的數(shù)量的氧和氮。潛水員有一定數(shù)量的氣缸。每個氣缸都有重量和氣體容量。潛水員為了完成他的工作需要特定數(shù)量的氧和氮

34、。他完成工作所需氣缸的總重的最低限度的是多少？w 例如：潛水員有5個氣缸。每行三個數(shù)字為：氧，氮的（升）量和氣缸的重量：w 3 36 120w 10 25 129w 5 50 250w 1 45 130w 4 20 119w 如果潛水員需要5升的氧和60升的氮則總重最小為249（1，2或者4，5號氣缸）。w 你的任務就是計算潛水員為了完成他的工作需要的氣缸的重量的最低值?！据斎敫袷捷斎敫袷健縲 第一行有2整數(shù)m,n（1=m=21,1=n=79）。它們表示氧，氮各自需要的量。w 第二行為整數(shù)k（1=n=1000）表示氣缸的個數(shù)。w 此后的k行，每行包括ai，bi，ci（1=ai=21，1=bi=

35、79，1=ci=800）3整數(shù)。這些各自是：第i個氣缸里的氧和氮的容量及汽缸重量?！据敵龈袷捷敵龈袷健縲 僅一行包含一個整數(shù)，為潛水員完成工作所需的氣缸的重量總和的最低值?！緟⒖汲绦颉俊緟⒖汲绦颉?include#include /初始化memset要用到using namespace std;int v, u, k;int a1001, b1001, c1001;int f101101;int main() memset(f,127,sizeof(f); /初始化為一個很大的正整數(shù) f00 = 0; scanf(%d%d%d,&v,&u,&k); for (int i

36、 = 1; i = k; i+) scanf(%d%d%d,&ai,&bi,&ci); for (int i = 1; i = 0; j-) for (int l = u; l = 0; l-) int t1 = j+ ai,t2 = l + bi; if (t1 v) t1 = v; /若氮、氧含量超過需求，可直接用需求量代換， if (t2 u) t2 = u; /不影響最優(yōu)解 if (ft1t2 fjl + ci) ft1t2 = fjl + ci; printf(%d,fvu); return 0; w小結(jié)小結(jié) w 事實上，當發(fā)現(xiàn)由熟悉的動態(tài)規(guī)劃題目事實上，當發(fā)

37、現(xiàn)由熟悉的動態(tài)規(guī)劃題目變形得來的題目時，在原來的狀態(tài)中加一維變形得來的題目時，在原來的狀態(tài)中加一維以滿足新的限制是一種比較通用的方法。希以滿足新的限制是一種比較通用的方法。希望你能從本講中初步體會到這種方法。望你能從本講中初步體會到這種方法。 w六、分組的背包問題w問題w有N件物品和一個容量為V的背包。第i件物品的費用是wi，價值是ci。這些物品被劃分為若干組，每組中的物品互相沖突，最多選一件。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。w算法w這個問題變成了每組物品有若干種策略：是選擇本組的某一件，還是一件都不選。也就是說設fkv表示前k組物品花費費用v能取得

38、的最大權(quán)值，則有fkv=maxfk-1v，fk-1v-wi+ci|物品i屬于第k組。w使用一維數(shù)組的偽代碼如下：wfor 所有的組kw for v=V.0w for 所有的i屬于組kwfv=maxfv,fv-wi+ciw注意這里的三層循環(huán)的順序，“for v=V.0”這一層循環(huán)必須在“for 所有的i屬于組k”之外。這樣才能保證每一組內(nèi)的物品最多只有一個會被添加到背包中。w另外，顯然可以對每組中的物品應用完全背包中“一個簡單有效的優(yōu)化”?！纠纠?】分組背包分組背包【問題描述問題描述】w 一個旅行者有一個最多能用V公斤的背包，現(xiàn)在有n件物品，它們的重量分別是W1，W2，.,Wn，它們的價值分別

39、為C1,C2,.,Cn。這些物品被劃分為若干組，每組中的物品互相沖突，最多選一件。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大?！据斎敫袷捷斎敫袷健縲 第一行：三個整數(shù)，V(背包容量，V=200)，N(物品數(shù)量，N=30)和T(最大組號，T=10)；w 第2.N+1行：每行三個整數(shù)Wi,Ci,P，表示每個物品的重量，價值，所屬組號。【輸出格式】【輸出格式】w 僅一行，一個數(shù)，表示最大總價值?！緲永斎搿俊緲永斎搿縢roup.inw10 6 3w2 1 1w3 3 1w4 8 2w6 9 2w2 8 3w3 9 3【樣例輸出】【樣例輸出】group.outw20【

40、參考程序】【參考程序】#includeusing namespace std;int v, n, t;int w31, c31;int a1132, f201;int main() scanf(%d%d%d,&v,&n,&t); for (int i = 1; i = n; i+) int p; scanf(%d%d%d,&wi,&ci,&p); ap+ap0 = i; for (int k = 1; k = 0; j-) for (int i = 1; i = waki) int tmp = aki; if (fj fj-wtmp+ctmp)

41、fj = fj-wtmp+ctmp; printf(%d,fv); return 0;小結(jié)小結(jié) 分組的背包問題將彼此互斥的若干物品稱為一個組，這建立了一個很好的模型。不少背包問分組的背包問題將彼此互斥的若干物品稱為一個組，這建立了一個很好的模型。不少背包問題的變形都可以轉(zhuǎn)化為分組的背包問題。題的變形都可以轉(zhuǎn)化為分組的背包問題。 七、有依賴的背包問題七、有依賴的背包問題w簡化的問題簡化的問題 w 這種背包問題的物品間存在某種這種背包問題的物品間存在某種“依賴依賴”的關(guān)系。也就是說，的關(guān)系。也就是說，i依賴于依賴于j，表，表示若選物品示若選物品i，則必須選物品，則必須選物品j。為了簡化起見，我們先

42、設沒有某個物品既依賴于。為了簡化起見，我們先設沒有某個物品既依賴于別的物品，又被別的物品所依賴；另外，沒有某件物品同時依賴多件物品。別的物品，又被別的物品所依賴；另外，沒有某件物品同時依賴多件物品。 w算法算法w 這個問題由NOIP2006金明的預算方案金明的預算方案一題擴展而來。遵從該題的提法，將不依賴于別的物品的物品稱為“主件”，依賴于某主件的物品稱為“附件”。由這個問題的簡化條件可知所有的物品由若干主件和依賴于每個主件的一個附件集合組成。 w 按照背包問題的一般思路，僅考慮一個主件和它的附件集合?？墒?，可用的策略非常多，包括：一個也不選，僅選擇主件，選擇主件后再選擇一個附件，選擇主件后再

43、選擇兩個附件無法用狀態(tài)轉(zhuǎn)移方程來表示如此多的策略。（事實上，設有n個附件，則策略有2n+1個，為指數(shù)級。） w 考慮到所有這些策略都是互斥的（也就是說，你只能選擇一種策略），所以一個主件和它的附件集合實際上對應于分組的背包分組的背包中的一個物品組，每個選擇了主件又選擇了若干個附件的策略對應于這個物品組中的一個物品，其費用和價值都是這個策略中的物品的值的和。但僅僅是這一步轉(zhuǎn)化并不能給出一個好的算法，因為物品組中的物品還是像原問題的策略一樣多。 w 再考慮分組的背包分組的背包中的一句話： 可以對每組中的物品應用完全背包完全背包中“一個簡單有效的優(yōu)化”。這提示我們，對于一個物品組中的物品，所有費用相

44、同的物品只留一個價值最大的，不影響結(jié)果。所以，我們可以對主件i的“附件集合”先進行 一次01背包，得到費用依次為0.V-wi所有這些值時相應的最大價值f0.V-wi。那么這個主件及它的附件集合相當于V-wi+1個物品的物品組，其中費用為wi+k的物品的價值為fk+ci。也就是說原來指數(shù)級的策略中有很多策略都是冗余的，通過一次01背包后，將主件i轉(zhuǎn)化為 V-wi+1個物品的物品組，就可以直接應用分組的背包分組的背包的算法解決問題了。 w 更一般的問題是：更一般的問題是：依賴關(guān)系以圖論中“森林”的形式給出（森林即多叉樹的集合），也就是說，主件的附件仍然可以具有自己的附件集合，限制只是每個物品最多只依賴于一個物品（只有一個主件）且不出現(xiàn)循環(huán)依賴。 w 解決這個問題仍然可以用將每個主件及其附件集合轉(zhuǎn)化為物品組的方式。唯一不同的是，由于附件可能還有附件，就不能將每個附件都看作一個一般的01 背包中的物品了。若這個附件也有附件集合，則它必定要被先轉(zhuǎn)化為物品組，然后用分組的背包問題解出主件及其附件集合所對應的附件組中各個費用的附件所對應的價值。 w 事實上，這是一種樹形DP，其特點是每個父節(jié)點都需要對它的各個兒子的屬性進行一次DP以求得自己的相關(guān)屬性。這已經(jīng)觸及到了“泛化物品”的思想。看完后，你會發(fā)現(xiàn)這個“依賴關(guān)系樹”每一個子樹都等價于一件泛化物品，