完全背包问题（动态规划法-DP含一维滚动数组优化）

完全背包问题：
有n个重量分别为{w1，w2，…，wn}的物品，它们的价值分别为{v1，v2，…，vn}，给定一个容量为W的背包。小偷要选择从这些物品中偷一部分物品放入该背包的方案，每个物品可以偷任意个，要求选中的物品不仅能够放到背包中，而且重量和为W具有最大的价值。
该题是0-1背包问题的扩展，0-1背包是某个物品偷或者不偷，完全背包是某个物品要偷多少个？
从0-1背包问题那我们推断出了一个状态转移公式：
B(i,w) = max( B(i-1,w) ,B(i-1,w-c(i))+v(i) )
其中,i=前i件物品，w=可用容量 c(i)=第i件物品容量，v(i)=第i件物品价值
对该公式不明白的可以参考我前面写的0-1背包问题DP
所以，我们很容易推导出完全背包问题的状态转移公式：

    B(i,w) = max( B(i-1,w) ,B(i-1,w-c(i)*k)+v(i)*k )      1=<k<=[V/c(i)] ,V为总可用容量，是w的最大值  

如此，我们可以模拟0-1背包问题写一个三层嵌套循环，然而写起来并不优美，这个式子其实可以再简化，我们推导一下：

1. B(i,w) = max( B(i-1,w) ,B(i-1,w-c(i)* k)+v(i)* k ) ：1=<k<=[V/c(i)] 我们观察B(i-1,w-c(i)* k)+v(i)* k 让 k=k'+1，或者你也可以取k=x+1,k=y+1都行，k'只是一个新的系数表示
2. 这样一来，B(i-1,w-c(i)* k)+v(i)* k ：1=<k<=[V/c(i)] 转换到<==> B(i-1,w-c(i)-c(i)* k')+v(i)* k'+v(i) ：0=<k'<=[V/c(i) -1]
3. 另外（1）式可以表示为：B(i,w) = max( B(i-1,w-c(i)* k)+v(i)* k ) ：0=<k<=[V/c(i)]
4. 同样 B(i,w-c(i)) = max( B(i-1,w-c(i)-c(i)* k)+v(i)* k ) ： 0=<k<=[V/c(i)-1]
   观察一下，（2）式的右边和上面这个（4）式的右边是一摸一样的，所以得到了简化式
   B(i,w) =max( B(i-1,w), B(i,w-c(i)) + v(i))
   时间复杂度减少了，因为少了一个嵌套循环

还可以优化下空间复杂度。就像0-1背包问题一样，我们做一维滚动数组优化。因为B(i,w)仅仅依赖于B(i-1,w)和B(i,w-c(i));
最终得到 B(w) =max( B(w), B(w-c(i)) + v(i)) 1=<k<=[V/c(i)]

伪代码：

请注意for v = c[i] ... V 这和0-1背包问题是反向的因为B(i,w)用到了B(i,w-c(i));新值哦
for v = 0 ... V do B[v] = 0
    for i = 1 ... N do
      for w = c[i] ... V do
          B[w] = max{B[w], B[w-c[i]] + v[i]}

二维转一维你需要了解一下滚动数组这个东西，然后完全背包的二维公式是 B(i,w) =max( B(i-1,w), B(i,w-c(i)) + v(i)) ，下标有i代表的都是新值，有i-1代表的都是旧值，转成一维后是 B(w) =max( B(w), B(w-c(i)) + v(i)) ，当然如果要理解顺序问题的话得这么写： B(w)新 =max( B(w)旧, B(w-c(i))新 + v(i)) ，你想下x=max(x,y)这个式子，y对应B(w-c(i)),x是B(w)。w-c(i)比w小，所以要先处理小的，循环从小往大更新

上Java代码:

/**
 * @author  JaJIng
 */
class KnapSack{
    private static final int N = 5;//商品种类
    private static final int C = 20;//总可用容量
    private static final int w[]={2,3,4,5,9};  //每个商品容量
    private static final int v[]={3,4,5,8,10}; //每个商品价值

    public static void main(String[] args) {
        KnapSack knapSack = new KnapSack();
        int bfull[] = knapSack.callFull();
        System.out.println(bfull[20);

    }
     //完全背包  ...
    public int[] callFull(){
        //计算用
        int B[] = new int[C+1];
        for(int n=0;n<N;n++){
            for(int c=w[n];c<=C;c++){
                B[c] = Math.max(B[c],B[c-w[n]]+v[n]);
            }
        }
        return B;
    }