完全背包问题（一维）

题目

有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循环的位置可以颠倒位置，至于为什么，画图就知道了。至于为什么颠倒位置，当然是有必要时候带来时间上的优化了。