背包問題:運籌學術語-中文百科頻道

應用

1998年的石溪布魯克大學算法庫的研究表明，在75個算法問題中，背包問題是第18個最受歡迎，第4個最需要解決的問題（前三為後kd樹，後綴樹和bin包裝問題）。

背包問題出現在各種領域的現實世界的決策過程中，例如尋找最少浪費的方式來削減原材料，選擇投資和投資組合，選擇資産支持資産證券化，和生成密鑰為Merkle-Hellman和其他背包密碼系統。

背包算法的一個早期應用是在測試的構建和評分中，測試者可以選擇他們回答哪些問題。對于小例子來說，這是一個相當簡單的過程，為測試者提供這樣的選擇。例如，如果考試包含12個問題，每個問題的價值為10分，測試者隻需回答10個問題即可獲得100分的最高分。然而，在點值的異質分布的測試 - 即不同的問題值得不同的點值 - 更難以提供選擇。 Feuerman和Weiss提出了一個系統，其中學生被給予一個異質測試，共有125個可能的點。學生被要求盡可能回答所有的問題。在總點數加起來為100的問題的可能子集中，背包算法将确定哪個子集給每個學生最高的可能得分。

定義

我們有n種物品，物品j的重量為wj，價格為pj。

我們假定所有物品的重量和價格都是非負的。背包所能承受的最大重量為W。

如果限定每種物品隻能選擇0個或1個，則問題稱為0-1背包問題。

可以用公式表示為：

最大化

受限于

如果限定物品j最多隻能選擇bj個，則問題稱為有界背包問題。

可以用公式表示為：

最大化

受限于

如果不限定每種物品的數量，則問題稱為無界背包問題。

各類複雜的背包問題總可以變換為簡單的0-1背包問題進行求解。

基礎背包

題目

有N件物品和一個容量為V的背包。第i件物品的重量是w[i]，價值是v[i]。求解将哪些物品裝入背包可使這些物品的重量總和不超過背包容量，且價值總和最大。

基本思路

這是最基礎的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。

用子問題定義狀态：即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀态轉移方程便是：

f[i][v]=max{ f[i-1][v], f[i-1][v-w[i]]+v[i] }。

可以壓縮空間，f[v]=max{f[v],f[v-w[i]]+v[i]}

這個方程非常重要，基本上所有跟背包相關的問題的方程都是由它衍生出來的。所以有必要将它詳細解釋一下：“将前i件物品放入容量為v的背包中”這個子問題，若隻考慮第i件物品的策略（放或不放），那麼就可以轉化為一個隻牽扯前i-1件物品的問題。如果不放第i件物品，那麼問題就轉化為“前i-1件物品放入容量為v的背包中”，價值為f[i-1][v]；如果放第i件物品，那麼問題就轉化為“前i-1件物品放入剩下的容量為v-w[i]的背包中”，此時能獲得的最大價值就是f [i-1][v-w[i]]再加上通過放入第i件物品獲得的價值v[i]。

注意f[v]有意義當且僅當存在一個前i件物品的子集，其費用總和為f[v]。所以按照這個方程遞推完畢後，最終的答案并不一定是f[N] [V]，而是f[N][0..V]的最大值。如果将狀态的定義中的“恰”字去掉，在轉移方程中就要再加入一項f[v-1]，這樣就可以保證f[N] [V]就是最後的答案。至于為什麼這樣就可以，由你自己來體會了。

空間複雜

以上方法的時間和空間複雜度均為O(N*V），其中時間複雜度基本已經不能再優化了，但空間複雜度卻可以優化到O(V）。

先考慮上面講的基本思路如何實現，肯定是有一個主循環i=1..N，每次算出來二維數組f[i][0..V]的所有值。那麼，如果隻用一個數組f [0..V]，能不能保證第i次循環結束後f[v]中表示的就是我們定義的狀态f[i][v]呢？

f[i][v]是由f[i-1][v]和f [i-1][v-w[i]]兩個子問題遞推而來，能否保證在推f[v]時（也即在第i次主循環中推f[v]時）能夠得到f[v]和f[v -w[i]]的值呢？事實上，這要求在每次主循環中我們以v=V..0的順序推f[v]，這樣才能保證推f[v]時f[v-w[i]]保存的是狀态f[i-1][v-c[i]]的值。僞代碼如下：

for i=1..N

for v=V..0

f[v]=max{f[v],f[v-w[i]]+v[i]};

其中的f[v]=max{f[v],f[v-w[i]]}一句恰就相當于我們的轉移方程f[i][v]=max{f[i-1][v],f[i-1][v-w[i]]}，因為的

f[v-w[i]]就相當于原來的f[i-1][v-w[i]]。如果将v的循環順序從上面的逆序改成順序的話，那麼則成了f[i][v]由f[i][v-w[i]]推知，與本題意不符，但它卻是另一個重要的背包問題P02最簡捷的解決方案，故學習隻用一維數組解01背包問題是十分必要的。

示例程序

(完全背包問題求解)

#includeusing namespace std;int findM(int N,int K,int G[],int W[]){ int *M=new int[N+1],i,j,k; for(i=0;i M[i]=0; for(i=0;i { for(j=N;j>=G[i];j--) { for(k=1;j-k*G[i]>=0;k++) { M[j]=M[j]>k*W[i]+M[j-k*G[i]]?M[j]:k*W[i]+M[j-k*G[i]]; } } } return M[N];}int main(){ int N,K,i; while(cin>>N>>K) { int *G=new int[K]; int *W=new int[K]; for(i=0;i cin>>G[i]>>W[i]; cout< delete []G; delete []W; } return 0;}

遞歸實現

//現在設A[i][v]表示在剩餘空間為v時選取當前物品i的最大值，B[i][v]表示不選取當前物品i的最大值，所以總的最大值必然是max(A[n][v],B[n][v]），詳細程序見如下：

#include#includeusing namespace std;#define MAXSIZE 1000int A[MAXSIZE+1][MAXSIZE+1],B[MAXSIZE+1][MAXSIZE+1];int c[MAXSIZE+1],w[MAXSIZE+1];int F(int n ,int v){if(n==0)return 0;if(!A[n][v]&&v>=c[n])A[n][v]=F(n-1,v-c[n])+w[n];if(!B[n][v])B[n][v]=F(n-1,v);return A[n][v]>B[n][v]?A[n][v]:B[n][v];}int main(int argc,char*argv[]){int n,v;memset(A,0,sizeof(A));memset(B,0,sizeof(B));ifstreamin("in.txt");ofstreamout("out.txt");cin>>n>>v;for(int i=1;i<=n;i++)cin>>c[i]>>w[i];cout<return 0;}

程序

程序一：

vari,j,v,n:longint;f,c,w:array[0..100] of longint;function max(a,b:longint):longint;beginif a>b then exit(a) else exit(b);end;beginread(n,v);fillchar(f,sizeof(f),0);for i:=1 to n doread(c[i],w[i]);for i:=1 to n dofor j:=v downto c[i] dof[j]:=max(f[j],f[j-c[i]]+w[i]);writeln(f[v]);end.

程序二（順推法）：

var m,n,x,i:integer;c,w:array[1..30] of integer;f:array[0..30,0..300] of integer;function max(x,y:integer):integer;beginif x>y then max:=x else max:=y;end;beginreadln(n,m);for i:=1 to n doreadln(c[i],w[i]);for i:=1 to n dofor x:=1 to m doif x>=c[i] then f[i,x]:=max(f[i-1,x-c[i]]+w[i],f[i-1,x])else f[i,x]:=f[i-1,x];writeln(f[n,m]);end.

測試數據

//in.txt：

5 100

77 92

22 22

29 87

50 46

99 90

//out.txt

133

//in.txt：

8 200

79 83

58 14

86 54

11 79

28 72

62 52

15 48

68 62

//out.txt

334

C動态規劃算法的實現（完整代碼）

#include#includetypedefstruct{intobject;intweight;intvalue;}KnapSack;KnapSack*knapsack;//背包數組，用malloc或new動态創建intnum;//物體的個數intcontainer;//背包的最大容量int**array=NULL;//用來存放子問題的結果//動态創建背包voidCreate_KnapSack(){charc;printf("inputthenumberofobjectsn");scanf("%d",&num);knapsack=newKnapSack[num+1];printf("inputweightandvalueof%dobjects,like1:410n",num);for(inti=1;i<=num;i++){scanf("%d%c%d%c%d",&knapsack[i].object,&c,&knapsack[i].weight,&c,&knapsack[i].value);getchar();//為了獲取空格或其他輸入，聲明下scanf挺惡心}intk=knapsack[num].value;printf("%d",k);printf("inputthevolumeoftheknapsack:n");scanf("%d",&container);}//确定最優子問題voidResolve_KnapSack(){intk=knapsack[num].value;printf("%d",k);//創建動态二維數組m[num][container]array=(int**)malloc((num+1）*sizeof(int*));for(inti=0;i<=num;i++)array[i]=(int*)malloc((container+1）*sizeof(int));//for(intj=0;j<=container;j++)array[num][j]=(j>=knapsack[num].weight)?knapsack[num].value:0;//子問題的最優結果for(intm=num-1;m>0;m--)for(intn=0;n<=container;n++)if(n>knapsack[m].weight&&array[m+1][n]<=array[m+1][n-knapsack[m].weight]+knapsack[m].value)array[m][n]=array[m+1][n-knapsack[m].weight]+knapsack[m].value;//else包括兩種情況，共同點是該物體沒有被使用elsearray[m][n]=array[m+1][n];}//往回找，确定某個物體i是否被使用bool*Trace_back(){intc=container;bool*used;used=(bool*)malloc(sizeof(bool)*(num+1））；for(inti=1;iif(array[i][c]==array[i+1][c])used[i]=0;else{used[i]=1;c-=knapsack[i].weight;}used[num]=(c>=knapsack[num].weight)?1:0;returnused;}//用來輸出被使用的物體及其相關值voidPrint_KnapSack(bool*used){printf("theobjectsusedasfollows:n");for(inti=1;i<=num;i++)if(used[i])printf("%d:%d%dn",knapsack[i].object,knapsack[i].weight,knapsack[i].value);}voidmain(){bool*used;Create_KnapSack();Resolve_KnapSack();used=Trace_back();Print_KnapSack(used);}

總結

0/1背包問題是最基本的背包問題，它包含了背包問題中設計狀态、方程的最基本思想，另外，别的類型的背包問題往往也可以轉換成0/1背包問題求解。故一定要仔細體會上面基本思路的得出方法，狀态轉移方程的意義，以及最後怎樣優化的空間複雜度。

完全背包

題目

有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的體積是c，價值是w。将哪些物品裝入背包可使這些物品的體積總和不超過背包容量，且價值總和最大。

基本思路

這個問題非常類似于01背包問題，所不同的是每種物品有無限件。也就是從每種物品的角度考慮，與它相關的策略已并非取或不取兩種，而是有取0件、取1件、取2件……等很多種。如果仍然按照解01背包時的思路，令f[i,v]表示前i種物品恰放入一個容量為v的背包的最大權值。仍然可以按照每種物品不同的策略寫出狀态轉移方程，像這樣：f[i,v]=max{f[i,v-vi]+wi,f[i-1,v]}。這跟01背包問題一樣有O(N*V）個狀态需要求解，但求解每個狀态的時間則不是常數了，求解狀态f[v]的時間是O(v/c），總的複雜度是超過O(VN）的。

将01背包問題的基本思路加以改進，得到了這樣一個清晰的方法。這說明01背包問題的方程的确是很重要，可以推及其它類型的背包問題。但我們還是試圖改進這個複雜度。

簡單有效

完全背包問題有一個很簡單有效的優化，是這樣的：若兩件物品i、j滿足c<=c[j]且w>=w[j]，則将物品j去掉，不用考慮。這個優化的正确性顯然：任何情況下都可将價值小體積高的j換成物美價廉的i，得到至少不會更差的方案。對于随機生成的數據，這個方法往往會大大減少物品的件數，從而加快速度。然而這個并不能改善最壞情況的複雜度，因為有可能特别設計的數據可以一件物品也去不掉。

完全背包還有另一種優化，代碼如下：

var p,t:array[1..10000] of integer;m,n:integer;min:longint; procedure init;var i:integer;beginreadln(m,n);min:=maxlongint;for i:=1 to n dobeginreadln(p[i],t[i]);if t[i]end;end; procedure qsort(l,r:integer);var i,j,x,temp:longint;begini:=l;j:=r;x:=t[(l+r)div2];while ibeginwhile(iwhile(iif i<=j thenbegintemp:=t[i];t[i]:=t[j];t[j]:=temp;temp:=p[i];p[i]:=p[j];p[j]:=temp;inc(i);dec(j);end;end;if iif lend; function max(a,b:longint):longint;beginif a>b then max:=a else max:=b;end; procedure work;var f:array[0..10000] of longint;i,j:longint;beginfillchar(f,sizeof(f),0);for i:=min to m dobeginf[i]:=f[i-1];for j:=1 to n doif i-t[j]>=0 then f[i]:=max(f[i],f[i-t[j]]+p[j]) else break;end;writeln(f[m]);end; begininit;qsort(1,n);work;end.

轉為問題

既然01背包問題是最基本的背包問題，那麼我們可以考慮把完全背包問題轉化為01背包問題來解。最簡單的想法是，考慮到第i種物品最多選V/c 件，于是可以把第i種物品轉化為V/c件體積及價值均不變的物品，然後求解這個01背包問題。這樣完全沒有改進基本思路的時間複雜度，但這畢竟給了我們将完全背包問題轉化為01背包問題的思路：将一種物品拆成多件物品。

更高效的轉化方法是：把第i種物品拆成體積為c*2^k、價值為w*2^k的若幹件物品，其中k滿足c*2^k for i=1..N for v=0..V f[v]=max{f[v],f[v-c]+w};

你會發現，這個僞代碼與P01的僞代碼隻有v的循環次序不同而已。為什麼這樣一改就可行呢？首先想想為什麼P01中要按照v=V..0的逆序來循環。這是因為要保證第i次循環中的狀态f[v]是由狀态f[v-c]遞推而來。換句話說，這正是為了保證每件物品隻選一次，保證在考慮“選入第i件物品”這件策略時，依據的是一個絕無已經選入第i件物品的子結果f[v-c]。而完全背包的特點恰是每種物品可選無限件，所以在考慮“加選一件第i種物品”這種策略時，卻正需要一個可能已選入第i種物品的子結果f[v-c]，所以就可以并且必須采用v= 0..V的順序循環。這就是這個簡單的程序為何成立的道理。

這個算法也可以以另外的思路得出。例如，基本思路中的狀态轉移方程可以等價地變形成這種形式：f[v]=max{f[v],f[v-c]+w}，将這個方程用一維數組實現，便得到了上面的僞代碼。

實現

vari,j,v,n:longint;f,c,w:array[0..100] of longint;functionmax(a,b:longint):longint;beginifa>bthenexit(a)elseexit(b);end;beginread(n,v);fillchar(f,sizeof(f),0);fori:=1tondoread(c[i],w[i]);fori:=1tondoforj:=c[i]tovdof[j]:=max(f[j],f[j-c[i]]+w[i]);writeln(f[v]);end.

總結

完全背包問題也是一個相當基礎的背包問題，它有兩個狀态轉移方程，分别在“基本思路”以及“O(VN）的算法“的小節中給出。希望你能夠對這兩個狀态轉移方程都仔細地體會，不僅記住，也要弄明白它們是怎麼得出來的，最好能夠自己想一種得到這些方程的方法。事實上，對每一道動态規劃題目都思考其方程的意義以及如何得來，是加深對動态規劃的理解、提高動态規劃功力的好方法。

多重問題

題目

有N種物品和一個容量為V的背包。第i種物品最多有n件可用，每件體積是c，價值是w。求解将哪些物品裝入背包可使這些物品的體積總和不超過背包容量，且價值總和最大。

基本算法

這題目和完全背包問題很類似。基本的方程隻需将完全背包問題的方程略微一改即可，因為對于第i種物品有n+1種策略：取0件，取1件……取 n件。令f[v]表示前i種物品恰放入一個容量為v的背包的最大權值，則：f[v]=max{f[v-k*c]+ k*w|0<=k<=n}。複雜度是O(V*∑n）。

轉為問題

另一種好想好寫的基該方法是轉化為01背包求解：把第i種物品換成n件01背包中的物品，則得到了物品數為∑n的01背包問題，直接求解，複雜度仍然是O(V*∑n）。

但是我們期望将它轉化為01背包問題之後能夠像完全背包一樣降低複雜度。仍然考慮二進制的思想，我們考慮把第i種物品換成若幹件物品，使得原問題中第i種物品可取的每種策略——取0..n件——均能等價于取若幹件代換以後的物品。另外，取超過n件的策略必不能出現。

方法是：将第i種物品分成若幹件物品，其中每件物品有一個系數，這件物品的費用和價值均是原來的費用和價值乘以這個系數。使這些系數分别為 1,2,4,...,2^(k-1），n-2^k+1，且k是滿足n-2^k+1>0的最大整數。例如，如果n為13，就将這種物品分成系數分别為1,2,4,6的四件物品。

分成的這幾件物品的系數和為n，表明不可能取多于n件的第i種物品。另外這種方法也能保證對于0..n間的每一個整數，均可以用若幹個系數的和表示，這個證明可以分0..2^k-1和2^k..n兩段來分别讨論得出，并不難，希望你自己思考嘗試一下。

這樣就将第i種物品分成了O(log n）種物品，将原問題轉化為了複雜度為O(V*∑log n）的01背包問題，是很大的改進。

算法

多重背包問題同樣有O(VN）的算法。這個算法基于基本算法的狀态轉移方程，但應用單調隊列的方法使每個狀态的值可以以均攤O⑴的時間求解。由于用單調隊列優化的DP已超出了NOIP的範圍，故本文不再展開講解。我最初了解到這個方法是在樓天成的“男人八題”幻燈片上。

小結

這裡我們看到了将一個算法的複雜度由O(V*∑n）改進到O(V*∑log n）的過程，還知道了存在應用超出NOIP範圍的知識的O(VN）算法。希望你特别注意“拆分物品”的思想和方法，自己證明一下它的正确性，并用盡量簡潔的程序來實現。

三種背包

問題

如果将P01、P02、P03混合起來。也就是說，有的物品隻可以取一次（01背包），有的物品可以取無限次（完全背包），有的物品可以取的次數有一個上限（多重背包）。應該怎麼求解呢？

背包混合

考慮到在P01和P02中最後給出的僞代碼隻有一處不同，故如果隻有兩類物品：一類物品隻能取一次，另一類物品可以取無限次，那麼隻需在對每個物品應用轉移方程時，根據物品的類别選用順序或逆序的循環即可，複雜度是O(VN）。僞代碼如下：

for i=1..N

if 第i件物品是01背包

for v=V..0

f[v]=max{f[v],f[v-c]+w};

else if 第i件物品是完全背包

for v=0..V

f[v]=max{f[v],f[v-c]+w};

再加上多重背包

如果再加上有的物品最多可以取有限次，那麼原則上也可以給出O(VN）的解法：遇到多重背包類型的物品用單調隊列解即可。但如果不考慮超過NOIP範圍的算法的話，用P03中将每個這類物品分成O(log n）個01背包的物品的方法也已經很優了。

小結

有人說，困難的題目都是由簡單的題目疊加而來的。這句話是否公理暫且存之不論，但它在本講中已經得到了充分的體現。本來01背包、完全背包、多重背包都不是什麼難題，但将它們簡單地組合起來以後就得到了這樣一道一定能吓倒不少人的題目。但隻要基礎紮實，領會三種基本背包問題的思想，就可以做到把困難的題目拆分成簡單的題目來解決。

二維費用

問題

二維費用的背包問題是指：對于每件物品，具有兩種不同的費用；選擇這件物品必須同時付出這兩種代價；對于每種代價都有一個可付出的最大值（背包容量）。問怎樣選擇物品可以得到最大的價值。設這兩種代價分别為代價1和代價2，第i件物品所需的兩種代價分别為a和b。兩種代價可付出的最大值（兩種背包容量）分别為V和U。物品的價值為w。

算法

費用加了一維，隻需狀态也加一維即可。設f[v]表示前i件物品付出兩種代價分别為v和u時可獲得的最大價值。狀态轉移方程就是：fi[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}。如前述方法，可以隻使用二維的數組：當每件物品隻可以取一次時變量v和u采用逆序的循環，當物品有如完全背包問題時采用順序的循環。當物品有如多重背包問題時拆分物品。

限制

有時，“二維費用”的條件是以這樣一種隐含的方式給出的：最多隻能取M件物品。這事實上相當于每件物品多了一種“件數”的費用，每個物品的件數費用均為1，可以付出的最大件數費用為M。換句話說，設f[v][m]表示付出費用v、最多選m件時可得到的最大價值，則根據物品的類型（01、完全、多重）用不同的方法循環更新，最後在f[0..V][0..M]範圍内尋找答案。

另外，如果要求“恰取M件物品”，則在f[0..V][M]範圍内尋找答案。

小結

事實上，當發現由熟悉的動态規劃題目變形得來的題目時，在原來的狀态中加一維以滿足新的限制是一種比較通用的方法。希望你能從本講中初步體會到這種方法。

分組背包

問題

有N件物品和一個容量為V的背包。第i件物品的費用是c，價值是w。這些物品被劃分為若幹組，每組中的物品互相沖突，最多選一件。求解将哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

算法

這個問題變成了每組物品有若幹種策略：是選擇本組的某一件，還是一件都不選。也就是說設f[k][v]表示前k組物品花費費用v能取得的最大權值，則有f[k][v]=max{f[k-1][v],f[k-1][v-c]+w|物品i屬于第k組}。

使用一維數組的僞代碼如下：

for 所有的組k

for v=V..0

for 所有的i屬于組k （我覺得循環順序應改成這樣，大家可以看一下以前的版本自己判斷）

f[v]=max{f[v],f[v-c]+w}

另外，顯然可以對每組中的物品應用P02中“一個簡單有效的優化”。

小結

分組的背包問題将彼此互斥的若幹物品稱為一個組，這建立了一個很好的模型。不少背包問題的變形都可以轉化為分組的背包問題（例如P07），由分組的背包問題進一步可定義“泛化物品”的概念，十分有利于解題。

依賴問題

簡化問題

這種背包問題的物品間存在某種“依賴”的關系。也就是說，i依賴于j，表示若選物品i，則必須選物品j。為了簡化起見，我們先設沒有某個物品既依賴于别的物品，又被别的物品所依賴；另外，沒有某件物品同時依賴多件物品。

算法

這個問題由NOIP2006金明的預算方案一題擴展而來。遵從該題的提法，将不依賴于别的物品的物品稱為“主件”，依賴于某主件的物品稱為“附件”。由這個問題的簡化條件可知所有的物品由若幹主件和依賴于每個主件的一個附件集合組成。

按照背包問題的一般思路，僅考慮一個主件和它的附件集合。可是，可用的策略非常多，包括：一個也不選，僅選擇主件，選擇主件後再選擇一個附件，選擇主件後再選擇兩個附件……無法用狀态轉移方程來表示如此多的策略。（事實上，設有n個附件，則策略有2^n+1個，為指數級。）

考慮到所有這些策略都是互斥的（也就是說，你隻能選擇一種策略），所以一個主件和它的附件集合實際上對應于P06中的一個物品組，每個選擇了主件又選擇了若幹個附件的策略對應于這個物品組中的一個物品，其費用和價值都是這個策略中的物品的值的和。但僅僅是這一步轉化并不能給出一個好的算法，因為物品組中的物品還是像原問題的策略一樣多。

再考慮P06中的一句話：可以對每組中的物品應用P02中“一個簡單有效的優化”。這提示我們，對于一個物品組中的物品，所有費用相同的物品隻留一個價值最大的，不影響結果。所以，我們可以對主件i的“附件集合”先進行一次01背包，得到費用依次為0..V-c所有這些值時相應的最大價值f'[0..V-c]。那麼這個主件及它的附件集合相當于V-c+1個物品的物品組，其中費用為c+k的物品的價值為f'[k]+w。也就是說原來指數級的策略中有很多策略都是冗餘的，通過一次01背包後，将主件i轉化為 V-c+1個物品的物品組，就可以直接應用P06的算法解決問題了。

一般問題

更一般的問題是：依賴關系以圖論中“森林”的形式給出（森林即多叉樹的集合），也就是說，主件的附件仍然可以具有自己的附件集合，限制隻是每個物品最多隻依賴于一個物品（隻有一個主件）且不出現循環依賴。

解決這個問題仍然可以用将每個主件及其附件集合轉化為物品組的方式。唯一不同的是，由于附件可能還有附件，就不能将每個附件都看作一個一般的01 背包中的物品了。若這個附件也有附件集合，則它必定要被先轉化為物品組，然後用分組的背包問題解出主件及其附件集合所對應的附件組中各個費用的附件所對應的價值。

事實上，這是一種樹形DP，其特點是每個父節點都需要對它的各個兒子的屬性進行一次DP以求得自己的相關屬性。這已經觸及到了“泛化物品”的思想。看完P08後，你會發現這個“依賴關系樹”每一個子樹都等價于一件泛化物品，求某節點為根的子樹對應的泛化物品相當于求其所有兒子的對應的泛化物品之和。

小結

NOIP2006的那道背包問題我做得很失敗，寫了上百行的代碼，卻一分未得。後來我通過思考發現通過引入“物品組”和“依賴”的概念可以加深對這題的理解，還可以解決它的推廣問題。用物品組的思想考慮那題中極其特殊的依賴關系：物品不能既作主件又作附件，每個主件最多有兩個附件，可以發現一個主件和它的兩個附件等價于一個由四個物品組成的物品組，這便揭示了問題的某種本質。

我想說：失敗不是什麼丢人的事情，從失敗中全無收獲才是。

泛化物品

定義

考慮這樣一種物品，它并沒有固定的費用和價值，而是它的價值随着你分配給它的費用而變化。這就是泛化物品的概念。

更嚴格的定義之。在背包容量為V的背包問題中，泛化物品是一個定義域為0..V中的整數的函數h，當分配給它的費用為v時，能得到的價值就是h(v）。

這個定義有一點點抽象，另一種理解是一個泛化物品就是一個數組h[0..V]，給它費用v，可得到價值h[V]。

一個費用為c價值為w的物品，如果它是01背包中的物品，那麼把它看成泛化物品，它就是除了h(c)=w其它函數值都為0的一個函數。如果它是完全背包中的物品，那麼它可以看成這樣一個函數，僅當v被c整除時有h(v)=v/c*w，其它函數值均為0。如果它是多重背包中重複次數最多為n的物品，那麼它對應的泛化物品的函數有h(v)=v/c*w僅當v被c整除且v/c<=n，其它情況函數值均為0。

一個物品組可以看作一個泛化物品h。對于一個0..V中的v，若物品組中不存在費用為v的的物品，則h(v)=0，否則h(v）為所有費用為v的物品的最大價值。P07中每個主件及其附件集合等價于一個物品組，自然也可看作一個泛化物品。

泛化物品

如果面對兩個泛化物品h和l，要用給定的費用從這兩個泛化物品中得到最大的價值，怎麼求呢？事實上，對于一個給定的費用v，隻需枚舉将這個費用如何分配給兩個泛化物品就可以了。同樣的，對于0..V的每一個整數v，可以求得費用v分配到h和l中的最大價值f(v）。也即f(v)=max{h(k) +l(v-k)|0<=k<=v}。可以看到，f也是一個由泛化物品h和l決定的定義域為0..V的函數，也就是說，f是一個由泛化物品h和 l決定的泛化物品。

由此可以定義泛化物品的和：h、l都是泛化物品，若泛化物品f滿足f(v)=max{h(k)+l(v-k)|0<=k<=v}，則稱f是h與l的和，即f=h+l。這個運算的時間複雜度是O(V^2）。

泛化物品的定義表明：在一個背包問題中，若将兩個泛化物品代以它們的和，不影響問題的答案。事實上，對于其中的物品都是泛化物品的背包問題，求它的答案的過程也就是求所有這些泛化物品之和的過程。設此和為s，則答案就是s[0..V]中的最大值。

問題泛化

一個背包問題中，可能會給出很多條件，包括每種物品的費用、價值等屬性，物品之間的分組、依賴等關系等。但肯定能将問題對應于某個泛化物品。也就是說，給定了所有條件以後，就可以對每個非負整數v求得：若背包容量為v，将物品裝入背包可得到的最大價值是多少，這可以認為是定義在非負整數集上的一件泛化物品。這個泛化物品——或者說問題所對應的一個定義域為非負整數的函數——包含了關于問題本身的高度濃縮的信息。一般而言，求得這個泛化物品的一個子域（例如0..V）的值之後，就可以根據這個函數的取值得到背包問題的最終答案。

綜上所述，一般而言，求解背包問題，即求解這個問題所對應的一個函數，即該問題的泛化物品。而求解某個泛化物品的一種方法就是将它表示為若幹泛化物品的和然後求之。

小結

本講可以說都是我自己的原創思想。具體來說，是我在學習函數式編程的 Scheme 語言時，用函數編程的眼光審視各類背包問題得出的理論。這一講真的很抽象，也許在“模型的抽象程度”這一方面已經超出了NOIP的要求，所以暫且看不懂也沒關系。相信随着你的OI之路逐漸延伸，有一天你會理解的。

我想說：“思考”是一個OIer最重要的品質。簡單的問題，深入思考以後，也能發現更多。

問法變化

以上涉及的各種背包問題都是要求在背包容量（費用）的限制下求可以取到的最大價值，但背包問題還有很多種靈活的問法。

例如，求解最多可以放多少件物品或者最多可以裝滿多少背包的空間。這都可以根據具體問題利用前面的方程求出所有狀态的值（f數組）之後得到。

還有，如果要求的是“總價值最小”“總件數最小”，隻需簡單的将上面的狀态轉移方程中的max改成min即可。

下面說一些變化更大的問法。

輸出方案

一般而言，背包問題是要求一個最優值，如果要求輸出這個最優值的方案，可以參照一般動态規劃問題輸出方案的方法：記錄下每個狀态的最優值是由狀态轉移方程的哪一項推出來的，換句話說，記錄下它是由哪一個策略推出來的。便可根據這條策略找到上一個狀态，從上一個狀态接着向前推即可。

還是以01背包為例，方程為f[v]=max{f[v],f[v-c]+w}。再用一個數組g [v]，設g[v]=0表示推出f[v]的值時是采用了方程的前一項（也即f[v]=f[v]），g[v]表示采用了方程的後一項。注意這兩項分别表示了兩種策略：未選第i個物品及選了第i個物品。那麼輸出方案的僞代碼可以這樣寫（設最終狀态為f[N][V]）：

i=N

v=V

while(i>0)

if(g[v]==0)

print "未選第i項物品"

else if(g[v]==1）

print "選了第i項物品"

v=v-c

另外，采用方程的前一項或後一項也可以在輸出方案的過程中根據f[v]的值實時地求出來，也即不須紀錄g數組，将上述代碼中的g [v]==0改成f[v]==f[v]，g[v]==1改成f[v]==f[v-c]+w也可。

輸出字典序最小的最優方案

這裡“字典序最小”的意思是1..N号物品的選擇方案排列出來以後字典序最小。以輸出01背包最小字典序的方案為例。

一般而言，求一個字典序最小的最優方案，隻需要在轉移時注意策略。首先，子問題的定義要略改一些。我們注意到，如果存在一個選了物品1的最優方案，那麼答案一定包含物品1，原問題轉化為一個背包容量為v-c[1]，物品為2..N的子問題。反之，如果答案不包含物品1，則轉化成背包容量仍為V，物品為2..N的子問題。不管答案怎樣，子問題的物品都是以i..N而非前所述的1..i的形式來定義的，所以狀态的定義和轉移方程都需要改一下。但也許更簡易的方法是先把物品逆序排列一下，以下按物品已被逆序排列來叙述。

在這種情況下，可以按照前面經典的狀态轉移方程來求值，隻是輸出方案的時候要注意：從N到1輸入時，如果f[v]==f及f[v]==f[f-c]+w同時成立，應該按照後者（即選擇了物品i）來輸出方案。