动态规划：完全背包理论基础

川长思鸟来 2023-10-16 16:42 55阅读 0赞

#### 动态规划：完全背包理论基础 ####

*  完全背包
 *  总结
 *  代码实现

## 完全背包 ##

有N件物品和一个最多能背重量为W的背包。

第i件物品的重量是weight\[i\]，得到的价值是value\[i\] 。

**每件物品都有无限个（也就是可以放入背包多次）**，求解将哪些物品装入背包里物品价值总和最大。

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

举例说明：  
背包最大重量为4。  
物品为：

**每件商品都有无限个！**

问背包能背的物品最大价值是多少？

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

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

for（int i = 0; i < weight.size(); 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.size(); i++){
         // 遍历物品
    	for(int j = weight[i]; j <= bagWeight; j++){
         // 遍历背包容量
    		dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    	}
    }

至于为什么，在**动态规划：关于01背包问题，你该了解这些！（滚动数组）** 中也做了讲解。

dp状态图如下：  
![在这里插入图片描述][b38e1d00111647ecacc6afc97df2ed5c.png]  
相信很多同学看网上的文章，关于完全背包介绍基本就到为止了。

**其实还有一个很重要的问题，为什么遍历物品在外层循环，遍历背包容量在内层循环？**

其实还有一个很重要的问题，为什么遍历物品在外层循环，遍历背包容量在内层循环？

难道就不能遍历背包容量在外层，遍历物品在内层？

看过这两篇的话：

*  **动态规划：关于01背包问题，你该了解这些！**
 *  **动态规划：关于01背包问题，你该了解这些！（滚动数组）**

就知道了，01背包中二维dp数组的两个for遍历的先后循序是可以颠倒了，一维dp数组的两个for循环先后循序一定是先遍历物品，再遍历背包容量。

**在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序是无所谓的！**

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

遍历物品在外层循环，遍历背包容量在内层循环，状态如图：  
![在这里插入图片描述][223ffe70670d495f9e41624a3bf68320.png]  
遍历背包容量在外层循环，遍历物品在内层循环，状态如图：  
![在这里插入图片描述][9b22a11330fa4ba0b979592a46e6811f.png]  
看了这两个图，大家就会理解，完全背包中，两个for循环的先后循序，都不影响计算dp\[j\]所需要的值（这个值就是下标j之前所对应的dp\[j\]）。

先遍历背包在遍历物品，代码如下：

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

## 总结 ##

细心的同学可能发现，**全文我说的都是对于纯完全背包问题，其for循环的先后循环是可以颠倒的**！

但如果题目稍稍有点变化，就会体现在遍历顺序上。

如果问装满背包有几种方式的话？ 那么两个for循环的先后顺序就有很大区别了，而leetcode上的题目都是这种稍有变化的类型。

这个区别，我将在后面讲解具体leetcode题目中给大家介绍，因为这块如果不结合具题目，单纯的介绍原理估计很多同学会越看越懵！

最后，**又可以出一道面试题了，就是纯完全背包，要求先用二维dp数组实现，然后再用一维dp数组实现，最后再问，两个for循环的先后是否可以颠倒？为什么？** 这个简单的完全背包问题，估计就可以难住不少候选人了。

## 代码实现 ##

//先遍历物品，再遍历背包
    private static void testCompletePack(){
        
        int[] weight = {
        1, 3, 4};
        int[] value = {
        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] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        for (int maxValue : dp){
        
            System.out.println(maxValue + "   ");
        }
    }
    
    //先遍历背包，再遍历物品
    private static void testCompletePackAnotherWay(){
        
        int[] weight = {
        1, 3, 4};
        int[] value = {
        15, 20, 30};
        int bagWeight = 4;
        int[] dp = new int[bagWeight + 1];
        for (int i = 1; i <= bagWeight; i++){
         // 遍历背包容量
            for (int j = 0; j < weight.length; j++){
         // 遍历物品
                if (i - weight[j] >= 0){
        
                    dp[i] = Math.max(dp[i], dp[i - weight[j]] + value[j]);
                }
            }
        }
        for (int maxValue : dp){
        
            System.out.println(maxValue + "   ");
        }
    }

**参考资料**：[代码随想录-动态规划：完全背包理论基础][-]

[b38e1d00111647ecacc6afc97df2ed5c.png]: https://img-blog.csdnimg.cn/b38e1d00111647ecacc6afc97df2ed5c.png
[223ffe70670d495f9e41624a3bf68320.png]: https://img-blog.csdnimg.cn/223ffe70670d495f9e41624a3bf68320.png
[9b22a11330fa4ba0b979592a46e6811f.png]: https://img-blog.csdnimg.cn/9b22a11330fa4ba0b979592a46e6811f.png
[-]: https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE