看這篇日志之前，請先閱讀我的上一篇日志，關于0/1背包的問題。
完全背包問題的描述：
有N 種物品和一個容量為V 的背包，每種物品都有無限件可用。第i 種物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。
可能大家已經看出來了，完全背包問題其實就是在0/1背包的問題的基礎上加了一個條件：每種物品都有無限件可用。
這個問題有不少解法，下面只給出最優化的O(VN)的算法。
這個算法使用一維數組，先看偽代碼：
for i=1..N
for v=0..V
f[v]=max{f[v],f[v-cost]+}
你會發現完全背包問題算法，這個偽代碼與01背包的偽代碼只有v 的循環次序不同而已。為什么這樣一改就可行呢？首先想想為什么01背包中要按照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的順序循環。這就是這個簡單的程序為何成立的道理。值得一提的是，上面的偽代碼中兩層for循環的次序可以顛倒。這個結論有可能會帶來算法時間常數上的優化。
這個算法也可以以另外的思路得出。
例如，將基本思路中求解f[i][v-c[i]]的狀態轉移方程顯式地寫出來：
f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}
把[i-1]和[i] 都去掉，就可以得到f[v]=max{f[v],f[v-c[i]]+w[i]}。為什么可以去掉呢?？匆幌律弦黄罩局械倪@個圖
你會發現，我們用二維數組 的解法做的時候，都是扣掉 當前的容量所剩下的容量最多能放多少，取的是上一行的數據： f[i-1][v]，這是因為在當前背包加入的之前，上一行就表示出了 加入上一個背包時的最優解。而其實每一行都比上一行優化，因為每往下走一行，就加入了一個背包，比原來的選擇多，得出的優化值自然比上一行的優化。
知道了每一行都比上一行優化之后 ，完全背包問題的答案就可以得出來了，我們每次都取當前行，即f[i][v]，那么原狀態方程就變成了：f[i][v]=max{f[i][v],f[i][v-c[i]]+w[i]}，呵呵，二維數組的第一維都變成i了完全背包問題算法，就是說都在同一行進行比較了。這樣的話就可以把它轉化成一維數組問題了。即，直接把[i]去掉。。。
最后抽象出處理一件完全背包類物品的過程偽代碼：
(cost,)
for v=cost..V
f[v]=max{f[v],f[v-c[i]]+w[i]}
上傳了一個參考文檔，有興趣的同志可以自己去看看