多重背包问题

多重背包问题

有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。

多重背包和01背包问题唯一不同的地方就是每件物品限制数量。

只要把Mi件物品分成多件独立的物品，那么就是01背包问题

例如：

背包最大重量为10。

物品为：

	重量	价值	数量
物品0	1	15	2
物品1	3	20	3
物品2	4	30	2

把多件物品都看成是独立的物品，那么就变为

	重量	价值	数量
物品0	1	15	1
物品0	1	15	1
物品1	3	20	1
物品1	3	20	1
物品1	3	20	1
物品2	4	30	1
物品2	4	30	1

代码

 public static void main(String[] args){

    int[] weight = {1,3,4}; //物品0，1，2的重量
    int[] value = {15,20,30}; //物品0，1，2的价值
    int[] nums = {2,3,2};//物品0，1，2的数量
    int bagweight = 10; //背包的容量
    multiBagProblem(weight,value,nums,bagweight);//90

}
//多重背包问题
public static void multiBagProblem(int[] weight, int[] value, int[] nums, int bagweight){
    List<Integer> item_weight = new ArrayList<>();
    List<Integer> item_value = new ArrayList<>();
    for(int i = 0; i < weight.length; i++){//把多重背包转化为01背包
            while(nums[i]>0){
                item_weight.add(weight[i]);
                item_value.add(value[i]);
                nums[i]--;
            }
    }
    int[] dp = new int[bagweight+1];
    for(int i = 0 ; i<item_weight.size(); i++){ //遍历物品
        for(int j = bagweight; j>=item_weight.get(i); j--) {
            dp[j] = Math.max(dp[j] , dp[j-item_weight.get(i)] + item_value.get(i));
        }
    }
    System.out.println("多重背包问题的答案为：" + dp[bagweight]);
}

• 时间复杂度：$O(m × n × k)$，m物品种类个数，n背包容量，k单类物品数量
• 空间复杂度：$O(n)$