问题描述

完全背包问题和01背包问题不同的在于，每一个物体的数量可以是无限的，每一个物体的重量为C[i]，其产生的价值为
W[i]，一共N件物品。背包的容量为V。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

问题求解

和01背包问题的区别在于，01背包问题当中对应的是一个物品放入或者不放入两种状态 但是完全背包问题每种物体的状态是放置
0,1,2,3...个

按照01背包问题思路，当前能获得的最大值和只和上一个放入背包的物品数量有关，转移方程记录为：

dp[i][v]=max(dp[i-1][v-c[i]*k])+w[i]*k // v-c[i]*k>=0, k=0,1,2...
dp[i][v]表示将第i种(不是前i个)物品放入容量为v的背包中，能够产生的最大收益

注意我们将第i个物品放入时，无论放入了多少个都是只计算一个占位(只按照一种计算)

具有VN个状态需要求解，但是每个状态的求解时间不是常数(因为v-c[i]k当中的k不是确定的)，未经优化的空间复杂度为O(VN)。时间复杂度可以认为是O(V∑(V/c[i]))，
重量为c[i]的物品，最多有V/c[i]件可以被装入背包中。

过程优化

对于本问题：不超过背包容量使得放入物品的收益最大，那么自然可以想到需要放置占用空间尽可能小且收益尽可能大的物体
如果物体i,j有c[i]>c[j] & w[i]<w[j] 那么直接丢弃物品i，因为物品i的性价比明显低于物品j。但是如果对于需要恰好填充满背包，那么不可随便丢弃物品。
这一优化过程的时间复杂度为O(N^2)的

转化为01背包问题

依据之前的时间复杂度的计算O(V∑(V/c[i]))可以知道，编号为i的物品最多可以被放入V/c[i]件，因此我们直接将
第i件物品拆分为V/c[i]件，每一件对应选取与否，这样的话可以直接转化为01背包问题。但是这样的拆分并没有改进时间复杂度。
更进一步的，我们将物品拆分为二进制表示，把第i种物品拆成费用为c[i]2^k、价值为w[i]2^k的若干件物品，其中k满足c[i]2^k<=V。
例如物品的c[i]=2, w[i]=2, V=10, 那么把物品拆分为c[i]=2,c[i+1]=4, c[i+2]=8；w[i]=2,w[i+1]=4, w[i+2]=8的三个物体。之后
这三个拆分的物体对应放入或者不放入背包中。因为背包中最多可以放入5个该物体，同时，放入1,2,3,4,5都可由这三种基础情况表示。据此可以减少时间和空间复杂度，.