動态規劃之背包問題-總結和拓展（二）

背包問題是在1978年由Merkel和Hellman提出的。它的主要思路是假定某人擁有大量物品，重量各不同。此人通過秘密地選擇一部分物品并将它們放 到背包中來加密消息。背包中的物品中重量是公開的，所有可能的物品也是公開的，但背包中的物品是保密的。附加一定的限制條件，給出重量，而要列出可能的物品，在計算上是不可實作的。背包問題是熟知的不可計算問題，背包體制以其加密，解密速度快而其人注目。但是，大多數一次背包體制均被破譯了，是以現在很少有人使用它。

P01：01背包問題

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

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

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

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

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

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

先考慮上面講的基本思路如何實作，肯定是有一個主循環i=1..N，每次算出來二維數組 f[0..V]的所有值。那麼，如果隻用一個數組f [0..V]，能不能保證第i次循環結束後f[v]中表示的就是我們定義的狀态f[v]呢？f[v]是由f[v]和f [v-c]兩個子問題遞推而來，能否保證在推f[v]時（也即在第i次主循環中推f[v]時）能夠得到f[v]和f[v -c]的值呢？事實上，這要求在每次主循環中我們以v=V..0的順序推f[v]，這樣才能保證推f[v]時f[v-c]儲存的是狀态f[v-c]的值。 僞代碼如下：

1 for i=1..N

2 for v=V..0

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

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

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

P02：完全背包問題

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

基本思路：這個問題非常類似于01背包問題，所不同的是每種物品有無限件。也就是從每種物品的角度考慮， 與它相關的政策已并非取或不取兩種，而是有取0件、取1件、取2件……等很多種。如果仍然按照解01背包時的思路，令f[v]表示前i種物品恰放入一個容 量為v的背包的最大權值。仍然可以按照每種物品不同的政策寫出狀态轉移方程，像這樣：f[v]=max{f[v-k*c]+k*w|0<=k*c& amp; lt;= 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，得到至少不會更差的方案。 對于随機生成的資料，這個方法往往會大大減少物品的件數，進而加快速度。然而這個并不能改善最壞情況的複雜度，因為有可能特别設計的資料可以一件物品也去不掉。

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

更高效的轉化方法是：把第i種物品拆成費用為c*2^k、價值為w*2^k的若幹件物品，其中 k滿足c*2^k