1、問題描述
已知:有一個容量為V的背包和N件物品，第i件物品的重量是weight[i]，收益是cost[i]。
條件:每種物品都有無限件，能放多少就放多少。
問題:在不超過背包容量的情況下，最多能獲得多少價值或收益
舉例：物品個數N = 3，背包容量為V = 5，則背包可以裝下的最大價值為40.
----------------------------------------------
2、基本思路（直接擴充01背包的方程）
由于本問題類似于01背包問題，在01背包問題中，物品要麼取，要麼不取，而在完全背包中，物品可以取0件、取1件、取2件...直到背包放不下位置。是以，可以直接在01背包的遞推式中擴充得到。
[cpp] view plain copy
- f[i][v]:表示前i件物品放入容量為v的容量中時的最大收益
- 遞推式：
- f[i][v] = max(f[i - 1][v],f[i - K * weight[i]] + K * Value[i]); 其中 1 <= K * weight[i] <= v,(v指此時背包容量)
- //初始條件
- f[0][v] = 0;
- f[i][0] = 0;
代碼：
[cpp] view plain copy
- #include <iostream>
- #include <assert.h>
- using namespace std;
- const int N = 3;
- const int V = 5;
- int weight[N + 1] = {0,3,2,2};
- int Value[N + 1] = {0,5,10,20};
- int f[N + 1][V + 1] = {0};
- int Completeknapsack()
- {
- //邊界條件
- for (int i = 0;i <= N;i++)
- {
- f[i][0] = 0;
- }
- for (int v = 0;v <= V;v++)
- {
- f[0][v] = 0;
- }
- //遞推
- for (int i = 1;i <= N;i++)
- {
- for (int v = 1;v <= V;v++)
- {
- f[i][v] = 0;
- int nCount = v / weight[i];
- for (int k = 0;k <= nCount;k++)
- {
- f[i][v] = max(f[i][v],f[i - 1][v - k * weight[i]] + k * Value[i]);
- }
- }
- }
- return f[N][V];
- }
- int main()
- {
- cout<<Completeknapsack()<<endl;
- system("pause");
- return 1;
- }
複雜度分析：
程式需要求解N*V個狀态，每一個狀态需要的時間為O（v/Weight[i]），總的複雜度為O(NV*Σ(V/c[i]))。
代碼優化：
完全背包問題有一個很簡單有效的優化，是這樣的：若兩件物品i、j滿足c[i]<=c[j]且w[i]>=w[j]，則将物品j去掉，不用考慮。
即，如果一個物品A是占的地少且價值高，而物品B是占地多，但是價值不怎麼高，那麼肯定是優先考慮A物品的。
這裡代碼略。
----------------------------------------------
3、轉換為01背包問題求解（直接利用01背包）
思路 1、完全背包的物品可以取無限件，根據背包的總容量V和第i件物品的總重量Weight[i],可知，背包中最多裝入V/Weight[i](向下取整)件該物品。是以可以直接改變第i件物品的總個數，使之達到V/Weight[i](向下取整)件，之後直接利用01背包的思路進行操作即可。
舉例：物品個數N = 3，背包容量為V = 5。
拆分之前的物品序列：
拆分之後的物品序列：
根據上述思想：在背包的最大容量（5）中，最多可以裝入1件物品一，是以不用擴充物品一。最多可以裝入2件物品二，是以可以擴充一件物品二。同理，可以擴充一件物品三。
時間複雜度的分析：O（NNew*V），其中V表示擴充前背包容量，NNew表示擴充後物品的個數，NNew =Σ(V/Weight[i](向下取整))
思路 2、對物品進行拆分時，拆成二進制的形式。
具體思路：把第i種物品拆成費用為weight[i]*2^k、價值為w[i]*2^k的若幹件物品，其中k滿足weight[i]*2^k<=V。
思路：這是二進制的思想，因為不管最優政策選幾件第i種物品，總可以表示成若幹個2^k件物品的和。
這樣把每種物品拆成O(log V/weight[i])件物品，是一個很大的改進。
舉例：物品個數N = 3，背包總容量為V = 5。
拆分之前的物品序列：
拆分之後的物品序列：
為了和前面的例子保持一緻，這裡才用之前的例子，但是這個例子沒有更好的說明二進制的拆分方法拆分的物品個數會少寫。
假設物品A的重量為2，收益為3，背包的總重量為20。
根據第一種拆分，可以拆成10個物品，每一個物品的重量為2，收益為3。
根據第二種拆分方法，可以拆成4個物品，分别是物品一（重量為1*2，收益為3），物品二（重量為2*2，收益為6），物品三（重量為4*2，收益為12），物品四（重量為8*2，收益為24）。
時間複雜度的分析：O（NNEW*V），其中V表示擴充前背包容量，NNew表示擴充後物品的個數，NNew = Σ(log V/weight[i](向下取整))
代碼：
[cpp] view plain copy
- #include <iostream>
- #include <vector>
- #include <assert.h>
- using namespace std;
- const int N = 3;
- const int V = 20;//5
- int weight[N + 1] = {0,3,2,2};
- int Value[N + 1] = {0,5,10,20};
- int NNew = 0;
- vector<int> weightVector;
- vector<int> Valuevector;
- int f[V + 1] = {0};
- void SplitItem()
- {
- //從1開始
- weightVector.push_back(0);
- Valuevector.push_back(0);
- //開始拆分
- int nPower = 1;
- for (int i = 1;i <= N;i++)
- {
- nPower = 1;
- while (nPower * weight[i] <= V)
- {
- weightVector.push_back(nPower * weight[i]);
- Valuevector.push_back(nPower * Value[i]);
- nPower <<= 1;
- }
- }
- }
- int Completeknapsack()
- {
- //拆分物品
- SplitItem();
- //轉化為01背包處理
- NNew = weightVector.size() - 1;//多加了一個0，要減去
- for (int i = 1;i <= NNew;i++)//物品個數變化
- {
- for (int v = V;v >= weightVector[i];v--)//背包容量仍是V
- {
- f[v] = max(f[v],f[v - weightVector[i]] + Valuevector[i]);
- }
- }
- return f[NNew];
- }
- int main()
- {
- cout<<Completeknapsack()<<endl;
- system("pause");
- return 1;
- }
4、O(VN)的算法
僞代碼
[cpp] view plain copy
- for (int i = 1;i <= N;i++)
- {
- for (int v = weight[i];v <= V;v++)
- {
- f[v] = max(f[v],f[v - weight[i]] + Value[i]);
- }
- }
分析：這和01背包的僞代碼很相似，在01背包的代碼中，v變化的區間是逆序循環的，即[V,Weight[i]]。而這裡，v變化的區間是順序循環的，即為[Weight[i],V]。
原因：
再次給出定義：
f[i][v]表示把前i件物品放入容量為v的背包時的最大代價。
f[i-1][v-c[i]]表示把前i - 1件物品放入容量為v的背包時的最大代價.
在01背包中，v變化的區間是逆序循環的原因：要保證由狀态f[i-1][v-c[i]]遞推狀态f[i][v]時，f[i-1][v-c[i]]沒有放入第i件物品。之後，在第i循環時，放入一件第i件物品。
01背包的方程：
[cpp] view plain copy
- f[i][v] = max(f[i - 1][v],f[i - 1][v - weight[i]] + Value[i])
在完全背包中，v變化的區間是順序循環的原因：完全背包的特點是每種物品可選無限件，在求解加選第i種物品帶來的收益f[i][v]時，在狀态f[i][v-c[i]]中已經盡可能多的放入物品i了，此時在f[i][v-c[i]]的基礎上，我們可以再次放入一件物品i，此時也是在不超過背包容量的基礎下，盡可能多的放入物品i。
完全背包的方程：
[cpp] view plain copy
- f[i][v] = max(f[i - 1][v],f[i][v - weight[i]] + Value[i]);
舉例：
物品個數N = 3，背包總容量為V = 5。
物品資訊：
完全背包：
分析：
i = 2，表示正在處理第2件物品。在求解f[2][4]時，如果要計算把第2件物品放入背包後的代價時，我們需要知道f[2][2],此時f[2][2]中已經盡全力放入第2件物品了（已經放入一件）。此時此刻還可以在放入一件第2件物品，在背包容量為4時，最多可以放入兩件第二件物品。
總結下，f[i][v]:表示在背包容量為v時，盡全力的放入第i件物品的代價。f[i][v - weight[i]]:表示在背包容量為v - weight[i]時，盡全力的放入第i件物品的代價。是以由f[i][v - weight[i]]轉換為f[i][v]時，也是在f[i][v - weight[i]]的基礎上有加入了一件物品i。
為了節省儲存狀态的空間，可以直接使用一維數組儲存狀态。
代碼：疊代方程：f[i][v] = max(f[i - 1][v],f[i][v - weight[i]] + Value[i]);
[cpp] view plain copy
- #include <iostream>
- #include <vector>
- #include <assert.h>
- using namespace std;
- const int N = 3;
- const int V = 5;//5
- int weight[N + 1] = {0,3,2,2};
- int Value[N + 1] = {0,5,10,20};
- int f[N + 1][V + 1] = {0};
- int Completeknapsack()
- {
- //初始化
- for (int i = 0;i <= N;i++)
- {
- f[i][0] = 0;
- }
- for (int v = 0;v <= V;v++)
- {
- f[0][v] = 0;
- }
- for (int i = 1;i <= N;i++)
- {
- for (int v = weight[i];v <= V;v++)
- {
- f[i][v] = max(f[i - 1][v],f[i][v - weight[i]] + Value[i]);
- }
- }
- return f[N][V];
- }
- int main()
- {
- cout<<Completeknapsack()<<endl;
- system("pause");
- return 1;
- }
代碼：疊代方程：f[v] = max(f[v],f[v - weight[i]] + Value[i]);
[cpp] view plain copy
- #include <iostream>
- using namespace std;
- const int N = 3;
- const int V = 5;//5
- int weight[N + 1] = {0,3,2,2};
- int Value[N + 1] = {0,5,10,20};
- int f[V + 1] = {0};
- int Completeknapsack()
- {
- f[0] = 0;
- for (int i = 1;i <= N;i++)
- {
- for (int v = weight[i];v <= V;v++)
- {
- f[v] = max(f[v],f[v - weight[i]] + Value[i]);
- }
- }
- return f[V];
- }
- int main()
- {
- cout<<Completeknapsack()<<endl;
- system("pause");
- return 1;
- }
轉自 http://blog.csdn.net/insistgogo/article/details/11081025