背包问题的疑惑

0/1背包要求为一件物品只有放或不放两种选择，所以二维写法为：
f[i][j]=max{f[i-1][j],f[i-1][j-v[i]]+w[i]}(j>=v[i])

而完全背包（也就是无限背包）是一种物品可以装无限个，按照上面的状态转移方程可改写为：
f[i][j]=max{f[i-1][j],f[i-1][j-k*v[i]]+k*w[i]} (k*v[i]<=j)
而这样写较为繁琐，可改为:
f[i][j]=max{f[i-1][j],f[i][j-v[i]]+w[i]}(j>=v[i])
这是因为，f[i][j-v[i]]可以看做f[i-1][j-(k-1)*v[i]]

若还有不懂的问题，请参阅DD_engi的“背包问题九讲”

题目
有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(VN)个状态需要求解，但求解每个状态的时间已经不是常数了，求解状态f[i][v]的时间是O(v/c[i])，总的复杂度可以认为是O(V*∑(V/c[i]))，是比较大的。

将01背包问题的基本思路加以改进，得到了这样一个清晰的方法。这说明01背包问题的方程的确是很重要，可以推及其它类型的背包问题。但我们还是试图改进这个复杂度。

一个简单有效的优化
完全背包问题有一个很简单有效的优化，是这样的：若两件物品i、j满足c[i]<=c