完全背包概述

完全背包

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

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

背包最大重量为4
物品为：

每件商品都有无限个！
问背包能背的物品最大价值是多少？

01背包和完全背包唯一不同就是体现在遍历顺序上，所以本文就不去做动规五部曲了，我们直接针对遍历顺序经行分析！


首先在回顾一下01背包的核心代码

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]);
    }
}

我们知道01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次

而完全背包的物品是可以添加多次的，所以要从小到大去遍历，即：

// 先遍历物品，再遍历背包
for(int i = 0; i < weight.length; i++) { // 遍历物品
    for(int j = weight[i]; j < bagWeight ; j++) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

dp状态图如下：

其实还有一个很重要的问题，为什么遍历物品在外层循环，遍历背包容量在内层循环？
大家都默认遍历物品在外层，遍历背包容量在内层，好像本应该如此一样，那么为什么呢？
难道就不能遍历背包容量在外层，遍历物品在内层？

• 之前有说过，01背包中二维dp数组的两个for遍历的先后循序是可以颠倒了，一维dp数组的两个for循环先后循序一定是先遍历物品，再遍历背包容量
• 在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序同样无所谓！

因为dp[j]是根据下标j之前所对应的dp[j]计算出来的。只要保证下标j之前的dp[j]都是经过计算的就可以了

遍历物品在外层循环，遍历背包容量在内层循环，状态如图：

遍历背包容量在外层循环，遍历物品在内层循环，状态如图：

完全背包中，两个for循环的先后循序，都不影响计算dp[j]所需要的值（这个值就是下标j之前所对应的dp[j]）

// 先遍历背包，再遍历物品
for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
    for(int i = 0; i < weight.length; i++) { // 遍历物品
        if (j - weight[i] >= 0) 
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

测试代码

// 先遍历物品，在遍历背包
public void test_CompletePack() {
    int[] weight = new int[]{1, 3, 4};
    int[] value = new int[]{15, 20, 30};
    int bagWeight = 4;
    int[] dp = new int[bagWeight + 1];
    for(int i = 0; i < weight.length; i++) { // 遍历物品
        for(int j = weight[i]; j <= bagWeight; j++) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
}
public static void main(String[] args) {
    test_CompletePack();
}

// 先遍历背包，再遍历物品
public void test_CompletePack() {
    int[] weight = new int[]{1, 3, 4};
    int[] value = new int[]{15, 20, 30};
    int bagWeight = 4;
    int[] dp = new int[bagWeight + 1];
    for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
        for(int i = 0; i < weight.length; i++) { // 遍历物品
            if (j - weight[i] >= 0) 
                dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
}
public static void main() {
    test_CompletePack();
}

总结

对于纯完全背包问题，其for循环的先后循环是可以颠倒的！
但如果题目稍稍有点变化，就会体现在遍历顺序上。
如果问装满背包有几种方式的话？那么两个for循环的先后顺序就有很大区别了