完全背包问题

完全背包问题

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

实例1：

背包最大重量为4

物品为：

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

解题思路

动态规划

参照01背包问题的核心代码

for(int i = 0 ; i < item_num; i++){ //遍历物品
    for(int j = bagweight; j>=weight[i]; j--) {//遍历背包容量，倒序遍历是为了保证物品i只被放入一次
        //dp[j]表示不放入物品i，dp[j-weight[i]]表示放入物品i
        dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

01背包问题遍历背包容量时从大到小遍历的可以保证每个物品仅被添加了一次

而完全背包问题物品可以添加多次，背包容量需要从小到大遍历

for(int i = 0 ; i < item_num; i++){ //遍历物品
    for(int j = weight[i]; j<=bagweight; j++) {//顺序遍历可以保证同一物品多次放入
        //dp[j]表示不放入物品i，dp[j-weight[i]]表示放入物品i
        dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

dp数组的状态如图

代码

public static void main(String[] args){
        int[] weight = {1,3,4}; //物品0，1，2的重量
        int[] value = {15,20,30}; //物品0，1，2的价值
        int bagweight = 4; //背包的容量
        completeBagProblem(weight, value, bagweight);

}
public static void  completeBagProblem(int[] weight, int[] value, int bagweight){
        int item_num = weight.length;
        //滚动数组
        //dp[j]为容量为j的背包所背的最大价值
        int[] dp = new int[bagweight+1];
        for(int i = 0 ; i < item_num; i++){ //遍历物品
            for(int j = weight[i]; j<=bagweight; j++) {//顺序遍历可以保证同一物品多次放入
                //dp[j]表示不放入物品i，dp[j-weight[i]]表示放入物品i
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }

        System.out.println("完全背包问题的答案为：" + dp[bagweight]);
   }

• 时间复杂度：$O(m × n)$ , m背包容量，n为物品的数量
• 空间复杂度：$O(m)$