背包問題

p01: 01背包問題

題目：有n件物品和一個容量為v的背包。第i件物品的費用是c[i]，價值是w[i]。求解将哪些物品裝入背包可使價值總和最大。

基本思路：這是最基礎的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。用子問題定義狀态：即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀态轉移方程便是：

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

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

優化空間複雜度

以上方法的時間和空間複雜度均為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-c[i]]兩個子問題遞推而來，能否保證在推f[i][v]時（也即在第i次主循環中推f[v]時）能夠得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事實上，這要求在每次主循環中我們以v=v..0的順序推f[v]，這樣才能保證推f[v]時f[v-c[i]]儲存的是狀态f[i-1][v-c[i]]的值。僞代碼如下：

for i = 1..n

for v = v..0

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

其中的f[v] = max{ f[v],f[v-c[i]] }一句恰就相當于我們的轉移方程f[i][v] = max{f[i-1][v],f[i-1][v-c[i]]}，因為現在的f[v-c[i]]就相當于原來的f[i-1][v-c[i]]。如果将v的循環順序從上面的逆序改成順序的話，那麼則成了f[i][v]由f[i][v-c[i]]推知，與本題意不符，但它卻是另一個重要的背包問題p02最簡捷的解決方案，故學習隻用一維數組解01背包問題是十分必要的。

01背包問題最常見的兩種問法: 

一是要求“恰好裝滿背包”時的最優解。

二是“沒有要求必須把背包裝滿”時的最優解。

這兩種問法的實作方法不同點主要在初始化上：

如果是第一種問法，要求恰好裝滿背包，那麼在初始化時除了f[0]為0其它f[1..v]均設為- ∞，這樣就可以保證最終得到的f[n]是一種恰好裝滿背包的最優解。

如果并沒有要求必須把背包裝滿，而是隻希望價格盡量大，初始化時應該将f[0..v]全部設為0。

p02: 完全背包問題

題目：有n種物品和一個容量為v的背包，每種物品都有無限件可用。第i種物品的費用是c[i]，價值是w[i]。求解将哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

基本思路：這個問題非常類似于01背包問題，所不同的是每種物品有無限件。也就是從每種物品的角度考慮，與它相關的政策已并非取或不取兩種，而是有取0件、取1件、取2件……等很多種。如果仍然按照解01背包時的思路，令f[i][v]表示

前i種物品恰放入一個容量為v的背包的最大權值。仍然可以按照每種物品不同的政策寫出狀态轉移方程，像這樣： 

f[i][v] = max{ f[i-1][v-k*c[i]]+k*w[i] | 0<=k*c[i]<=v } 

這跟01背包問題一樣有o(n*v)個狀态需要求解，但求解每個狀态的時間已經不是常數了，求解狀态f[i][v]的時間是o(v/c[i])，總的複雜度是超過o(vn)的。

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

但我們有更優的o(vn)的算法。這個算法使用一維數組，先看僞代碼：

for i = 1..n 

for v = 0..v 

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

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

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

最後抽象出處理一件完全背包類物品的過程僞代碼，以後會用到： 

procedure completepack(cost,weight) 

for v = cost..v 

f[v] = max{ f[v], f[v-cost]+weight }

p03: 多重背包問題

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

基本算法：這題目和完全背包問題很類似。基本的方程隻需将完全背包問題的方程略微一改即可，因為對于第i種物品有n[i]+1種政策：取0件，取1件……取n[i]件。令f[i][v]表示前i種物品恰放入一個容量為v的背包的最大權值，則有狀态轉移方程：

f[i][v] = max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]} 

複雜度是o(v*Σn[i])。

轉化為01背包問題

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

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

方法是：将第i種物品分成若幹件物品，其中每件物品有一個系數，這件物品的費用和價值均是原來的費用和價值乘以這個系數。使這些系數分别為1,2,4,...,2^(k-1),n[i]-2^k+1，且k是滿足n[i]-2^k+1>0的最大整數。例如，如果n[i]為13，就将這種物品分成系數分别為1,2,4,6的四件物品。 分成的這幾件物品的系數和為n[i]，表明不可能取多于n[i]件的第i種物品。另外這種方法也能保證對于0..n[i]間的每一個整數，均可以用若幹個系數的和表示，這個證明可以分0..2^k-1和2^k..n[i]兩段來分别讨論得出，并不難，希望你自己思考嘗試一下。

這樣就将第i種物品分成了o(log n[i])種物品，将原問題轉化為了複雜度為o(v*Σlog n[i])的01背包問題，是很大的改進。

下面給出o(log amount)時間處理一件多重背包中物品的過程，其中amount表示物品的數量： 

procedure multiplepack(cost,weight,amount) 

if cost*amount >= v 

{ 

completepack(cost,weight) 

return 

} 

integer k = 1 

while k<amount 

zeroonepack(k*cost,k*weight) 

amount = amount-k 

k = k*2 

zeroonepack(amount*cost,amount*weight)

希望你仔細體會這個僞代碼，如果不太了解的話，不妨翻譯成程式代碼以後，單步執行幾次，或者頭腦加紙筆模拟一下，也許就會慢慢了解了。

輸出方案

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

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

i=n 

v=v

while(i>0) 

if(g[i][v]==0) 

print "未選第i項物品" 

else if(g[i][v]==1) 

print "選了第i項物品" 

v=v-c[i]

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

本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。