多重背包

有N种物品和一个容量为V的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci，价值是Wi。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大
多重背包和01背包是非常像的，为什么和01背包像呢？
每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了

例如：
背包最大重量为10。
物品为：

问背包能背的物品最大价值是多少？
和如下情况有区别么？

毫无区别，这就转成了一个01背包问题了，且每个物品只用一次

这种方式来实现多重背包的代码如下：

public void test_multi_pack() {
    ArrayList<Integer> weight = new ArrayList<Integer>();
    weight.add(1);
    weight.add(3);
    weight.add(4);
    ArrayList<Integer> value = new ArrayList<Integer>();
    value.add(15);
    value.add(20);
    value.add(30);
    ArrayList<Integer> nums = new ArrayList<Integer>();
    nums.add(2);
    nums.add(3);
    nums.add(2);
    int bagWeight = 10;
    for (int i = 0; i < nums.length; i++) {
        while (nums[i] > 1) { // nums[i]保留到1，把其他物品都展开
            weight.add(weight[i]);
            value.add(value[i]);
            nums[i]--;
        }
    }
    int[] dp = new int[bagWeight + 1];
    for(int i = 0; i < weight.length; i++) { // 遍历物品
        for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
        for (int j = 0; j <= bagWeight; j++) {
            System.out.println("dp[j] = " + dp[j]);
        }
    }
    System.out.println("dp[bagWeight] = " + dp[bagWeight]);
}
public static void main() {
    test_multi_pack();
}

• 时间复杂度： m：物品种类个数，n背包容量，k单类物品数量