完全背包問題（一維）

題目

有N種物品和一個容量為V的背包，每種物品都可以無限次使用。

求解：将那些物品裝入背包，可以使物品消耗的費用總和不超過背包容量，且價值總和最大。

基本思路

這種題類似于01背包問題，不同的是每種物品有無數件，是以對于每一件物品就不是取還是不取的問題，

而是取幾件的問題。當然一種物品最多不會超過[V/Ci]件。我們先按照01背包問題思路了解

設f[i,v]前i種物品恰放入容量為v的背包中的最大值

狀态轉移方程

F[i,v]=max(f[i-1,v-k Ci]+kWi)(0<=k*Ci<=v)

雖然和01背包問題一樣有O(NV)個狀态求解，但是每個狀态的k是不确定的，是以每個狀态的時間也不再是常數，是以總的複雜度還是比較大的。

簡單優化

我們不妨想一下，我們想要價值最大化，所需要的物品必然是體積越小越好，價值越大越好，不過需要注意的是，

不是機關體積得價值越大越好。

是以，如果物品一的體積小于物品二，而且物品一的價值大于物品二，我們完全可以抛棄物品二。這是肯定的，

将價值小體積大的物品換成價值大體積小的物品，永遠不虧。當然這并不能改變最壞情況的時間複雜度，因為

有可能特别資料可以一件物品都不去掉。

這個優化可以簡單地O(N^2)實作，倒也可以接受。當然也可以用類似數排的方法，選取相同費用中價值最高的，

其餘的就可以抛棄了。

轉化為01背包問題

最簡單的想法是，将第i種物品轉換為[V/Ci]件費用和價值和i物品一樣的物品。這樣的時間複雜度沒有改進，

但是這指明了轉換為01背包的思路，将一種物品拆成多件隻能取或不取的物品。當然有更有效的辦法：把第i種

物品拆成費用為Ci2k、價值為Wi2k的若幹件物品，k滿足條件Ci2^k<=V。

這是一種二進制思想，這樣在時間複雜度上是一個很大的改進。

O(NV)的算法

這個算法使用一維數組：

for i–1 to N

for v–ci to V

f[v]–max(f[v],f[v-Ci]+Wi)

可以發現這隻是和01背包的僞代碼第二個循環的次序不同。

可是這又是為什麼呢？首先想想我們01背包為什麼按照v遞減的次序來循環，首先便是保留上一次循環留下的

資料也就是第i-1件物品的資料。也就是為了保證f[i,v]是由f[i-1,v-Ci]遞推而來，這也是01背包的關鍵，

該物品取還是不取。但是完全背包問題并不需要考慮取還是不取，它隻考慮取幾件。01背包的子問題的關鍵是

第i件物品和前i-1件物品的取法，而完全背包問題子問題的關鍵是容量V的最大價值，是以它所需要的子結果是

一個可能已經選入i件物品的子結果f[i,v-Ci]。

上面兩個for循環的位置可以颠倒位置，至于為什麼，畫圖就知道了。至于為什麼颠倒位置，當然是有必要時候帶來時間上的優化了。