完全背包，是一種經典的信息學問題，是研究一個固定容量的背包內能裝多大價值的東西的問題。
基本介紹
- 中文名：完全背包
- 屬於：一種經典的信息學問題
- 概念：研究固定容量背包能裝多大價值
- 類似於：01背包問題
完全背包問題,基本思路,簡單有效最佳化,最優解法—O,總結,
完全背包問題
題目
有N種物品和一個容量為V的背包，每種物品都有無限件可用。
第i種物品的體積是c，價值是w。求解將哪些物品裝入背包可使這些物品的體積總和不超過背包容量，且價值總和最大。
基本思路
這個問題非常類似於01背包問題，所不同的是每種物品有無限件，也就是從每種物品的角度考慮，與它相關的策略已並非取或不取兩種，而是有取0件、取1件、取2件……取[V/c]件等很多種。如果仍然按照解01背包時的思路，令f[v]表示前i種物品恰放入一個容量為v的背包的最大權值。仍然可以按照每種物品不同的策略寫出狀態轉移方程，像這樣：
f[j]=max{f[j],f[j-k*c]+k*w}（0<=k*c<=v）
這跟01背包問題一樣有O(N*V)個狀態需要求解，但求解每個狀態f[v]的時間是O(V/c)，總的複雜度是超過O(VN)的。
簡單有效最佳化
完全背包問題有一個很簡單有效的最佳化，是這樣的：若兩件物品i、j滿足c[i]<=c[j]且w[i]>=w[j]，則將物品j去掉，不用考慮。這個最佳化的正確性顯然：任何情況下都可將價值小費用高得j換成物美價廉的i，得到至少不會更差的方案。對於隨機生成的數據，這個方法往往會大大減少物品的件數，從而加快速度。然而這個並不能改善最壞情況的複雜度，因為有可能特別設計的數據可以一件物品也去不掉。這個最佳化可以簡單的O(N^2)地實現，一般都可以承受。
另外，針對背包問題而言，比較不錯的一種方法是：首先將費用大於V的物品去掉，然後使用類似計數排序的做法，計算出費用相同的物品中價值最高的是哪個，可以O(V+N)地完成這個最佳化。這個不太重要的過程就不給出偽代碼了，希望你能獨立思考寫出偽代碼或程式。
既然01背包問題是最基本的背包問題，那么我們可以考慮把完全背包問題轉化為01背包問題來解。最簡單的想法是，考慮到第i種物品最多選V/c件，於是可以把第i種物品轉化為V/c件費用為c[I]及價值w[I]的物品，然後求解這個01背包問題。這樣完全沒有改進基本思路的時間複雜度，但這畢竟給了我們將完全背包問題轉化為01背包問題的思路：將一種物品拆成多件物品。
更高效的轉化方法是：把第i種物品拆成費用為c*2^k、價值為w*2^k的若干件物品，其中k滿足0<=k<=log2(V/c)+1。這是二進制的思想，因為不管最優策略選幾件第i種物品，總可以表示成若干個2^k件物品的和。這樣把每種物品拆成O(log2(V/c))件物品，是一個很大的改進。
最優解法—O
for i=1..N
for j=c..V
f[j]=max{f[j],f[j-c]+w}
首先想想為什麼01背包中要按照v=V..0的逆序來循環。這是因為要保證第i次循環中的狀態f[v]是由狀態f[v-c]遞推而來。換句話說，這正是為了保證每件物品只選一次，保證在考慮“選入第i件物品”這件策略時，依據的是一個沒有已經選入第i件物品的子結果f[v-c]。
而當前完全背包的特點恰是每種物品可選無限件，所以在考慮“加選一件第i種物品”這種策略時，卻正需要一個可能已選入第i種物品的子結果f[v-c]，所以就可以並且必須採用v=0..V的順序循環。這就是這個簡單的程式為何成立的道理。
這個算法也可以以另外的思路得出。例如，基本思路中的狀態轉移方程可以等價地變形成這種形式：
f[j]=max{f[j],f[j-c]+w}
最後抽象出處理一件完全背包類物品的過程偽代碼，以後會用到：
procedure CompletePack(c,w)
for j=c..V
f[j]=max{f[j],f[j-c]+w}
範文：背包問題——“完全背包”詳解及實現（包含背包具體物品的求解）
總結
完全背包問題也是一個相當基礎的背包問題，它有兩個狀態轉移方程，分別在“基本思路”以及“最優解法—O(VN)”的小節中給出。希望你能夠對這兩個狀態轉移方程都仔細地體會，不僅記住，也要弄明白它們是怎么得出來的，最好能夠自己想一種得到這些方程的方法。
事實上，對每一道動態規劃題目都思考其方程的意義以及如何得來，是加深對動態規劃的理解、提高動態規劃功力的好方法。希望在你看完這篇文字後，會有所啟發。
