LeetCode刷题复盘笔记—一文搞懂纯完全背包问题（动态规划系列第十一篇）_leetcode 贪心 背包问题

今日主要总结一下动态规划背包问题的基础——纯完全背包问题

在Leetcode题库中主要都是0-1背包和完全背包的应用问题，所以主要掌握这两个背包问题·

题目：纯完全背包问题

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

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

同样leetcode上没有纯完全背包问题，都是需要完全背包的各种应用，需要转化成完全背包问题，所以我这里还是以纯完全背包问题进行讲解理论和原理。

在下面的讲解中，我依然举这个例子：

背包最大重量为4。

物品为：

本题重难点

每件商品都有无限个！

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

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

首先在回顾一下0-1背包的核心代码

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]);
    }
}
1
2
3
4
5

我们知道0-1背包内层的循环是从大到小（倒序）遍历，为了保证每个物品仅被添加一次。
而完全背包的物品是可以添加多次的，所以内层的循环要从小到大（正序）去遍历，即：

// 先遍历物品，再遍历背包
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]);

    }
}
1
2
3
4
5
6
7

dp状态图如下：

讲完了完全背包的代码之后其实还有一个很重要的问题，为什么遍历物品在外层循环，遍历背包容量在内层循环？

在一文搞懂纯0-1背包问题
我们讲过0-1背包中二维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.size(); i++) { // 遍历物品
        if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
    cout << endl;
}
1
2
3
4
5
6
7

---

总结

动态规划
英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。
动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的

对于动态规划问题，可以拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组
   以上的讲解可以开发一道面试题目（毕竟力扣上没原题）。

大家会发现，全文我说的都是对于纯完全背包问题也就是问凑成背包最大价值是多少的时候，其for循环的先后循环是可以颠倒的！

但如果题目稍稍有点变化不是求凑成背包最大价值是多少的时候，就不一定了，例如：

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

欢迎大家关注本人公众号：编程复盘与思考随笔

(关注后可以免费获得本人在csdn发布的资源源码)