0-1背包----完全背包

0-1背包使用一維數組

使用滾動數組将空間優化到了2*V，在背包九講中提到了使用一維數組也可以達到同樣的效果，個人認為這也是滾動思想的一種，由于使用一維數組解01背包會被多次用到，完全背包的一種優化實作方式也是使用一維數組，是以我們有必要了解這種方法。

如果隻使用一維數組f[0…v]，我們要達到的效果是：第i次循環結束後f[v]中所表示的就是使用二維數組時的f[i][v]，即前i個物體面對容量v時的最大價值。我們知道f[v]是由兩個狀态得來的，f[i-1][v]和f[i-1][v-c[i]]，使用一維數組時，當第i次循環之前時，f[v]實際上就是f[i-1][v]，那麼怎麼得到第二個子問題的值呢？事實上，如果在每次循環中我們以v=v…0的順序推f[v]時，就能保證f[v-c[i]]存儲的是f[i-1][v-c[i]]的狀态。狀态轉移方程為：

1 2	v = V...0; f(v) = max{ f(v), f(v-c[i])+w[i] }

我們可以與二維數組的狀态轉移方程對比一下

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

正如我們上面所說，f[v-c[i]]就相當于原來f[i-1][v-c[i]]的狀态。如果将v的循環順序由逆序改為順序的話，就不是01背包了，就變成完全背包了，這個後面說。這裡舉一個例子了解為何順序就不是01背包了

假設有物體z容量2，價值vz很大，背包容量為5，如果v的循環順序不是逆序，那麼外層循環跑到物體z時，内循環在v=2時，物體z被放入背包，當v=4時，尋求最大價值，物體z放入背包，f[4]=max{f[4],f[2]+vz}，這裡毫無疑問後者最大，那麼此時f[2]+vz中的f[2]已經裝入了一次物體z，這樣一來該物體被裝入背包兩次了就，不符合要求，如果逆序循環v，這一問題便解決了。

代碼如下，為了加深了解，可以在内循環結束輸出每一個狀态的情況到文本中，會發現與使用二維數組時的狀态轉移矩陣都是一樣一樣的。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

#include <iostream> using namespace std; int maxV[201];    int weight[11]; int value[11]; int V, N; void main() { int i, j; scanf("%d %d",&V, &N); for(i = 0; i < N; ++i) { scanf("%d %d",&weight[i],&value[i]); } for(i = 0; i < N; ++i) { for(j = V; j >= weight[i]; --j)   { int tmp = maxV[j-weight[i]]+value[i]; maxV[j] = (maxV[j] > tmp) ? maxV[j] : tmp; } } printf("%d",maxV[V]); }

可以看出，使用一維數組，代碼非常簡練。

完全背包問題

問題描述：

有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、j滿足c[i]<=c[j]且w[i]>=w[j]，則将物品j去掉，不用考慮。這個優化的正确性顯然：任何情況下都可将價值小費用高得j換成物美價廉的i，得到至少不會更差的方案。對于随機生成的資料，這個方法往往會大大減少物品的件數，進而加快速度。然而這個并不能改善最壞情況的複雜度，因為有可能特别設計的資料可以一件物品也去不掉。

這個優化可以簡單的O(N^2)地實作，一般都可以承受。另外，針對背包問題而言，比較不錯的一種方法是：首先将費用大于V的物品去掉，然後使用類似計數排序的做法，計算出費用相同的物品中價值最高的是哪個，可以O(V+N)地完成這個優化。這個不太重要的過程就不給出僞代碼了，希望你能獨立思考寫出僞代碼或程式。

轉化為01背包問題求解：

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

更高效的轉化方法是：把第i種物品拆成費用為c[i]*2^k、價值為w[i]*2^k的若幹件物品，其中k滿足c[i]*2^k<=V。這是二進制的思想，因為不管最優政策選幾件第i種物品，總可以表示成若幹個2^k件物品的和。這樣把每種物品拆成O(log(V/c[i]))件物品，是一個很大的改進。

但我們有更優的O(VN)的算法。

O(VN)的算法：

這個算法使用一維數組，先看代碼段：

1  for ( int i =  1; i <= N; i++)

2      for ( int v =  0; v <= V; v++)

3         f[v] = max(f[v], f[v - c[i]] + w[i]);

你會發現，這段代碼與01背包問題 的代碼隻有v的循環次序不同而已。為什麼這樣一改就可行呢？首先想想為什麼P01中要按照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的順序循環。這就是這個簡單的程式為何成立的道理。