背包问题理论基础完全背包 - 图1
参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！

完全背包

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

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

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

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

背包最大重量为4。

物品为：

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

每件商品都有无限个！

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

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

关于01背包我如下两篇已经进行深入分析了：

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

  1. for(int i = 0; i < weight.size(); i++) { // 遍历物品
  2.     for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
  3.         dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  4.     }
  5. }

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

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

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

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

dp状态图如下：

背包问题理论基础完全背包 - 图2

相信很多同学看网上的文章，关于完全背包介绍基本就到为止了。

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

这个问题很多题解关于这里都是轻描淡写就略过了，大家都默认 遍历物品在外层，遍历背包容量在内层，好像本应该如此一样，那么为什么呢？

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

看过这两篇的话：

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

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

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

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

背包问题理论基础完全背包 - 图3

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

背包问题理论基础完全背包 - 图4

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

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

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

C++测试代码

完整的C++测试代码如下：

  1. // 先遍历物品，在遍历背包
  2. void test_CompletePack() {
  3.     vector<int> weight = {1, 3, 4};
  4.     vector<int> value = {15, 20, 30};
  5.     int bagWeight = 4;
  6.     vector<int> dp(bagWeight + 1, 0);
  7.     for(int i = 0; i < weight.size(); i++) { // 遍历物品
  8.         for(int j = weight[i]; j <= bagWeight; j++) { // 遍历背包容量
  9.             dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  10.         }
  11.     }
  12.     cout << dp[bagWeight] << endl;
  13. }
  14. int main() {
  15.     test_CompletePack();
  16. }
  2. // 先遍历背包，再遍历物品
  3. void test_CompletePack() {
  4.     vector<int> weight = {1, 3, 4};
  5.     vector<int> value = {15, 20, 30};
  6.     int bagWeight = 4;
  8.     vector<int> dp(bagWeight + 1, 0);
  10.     for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
  11.         for(int i = 0; i < weight.size(); i++) { // 遍历物品
  12.             if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  13.         }
  14.     }
  15.     cout << dp[bagWeight] << endl;
  16. }
  17. int main() {
  18.     test_CompletePack();
  19. }

总结

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

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

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

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

别急，下一篇就是了！哈哈

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

其他语言版本

Java：

  1. //先遍历物品，再遍历背包
  2. private static void testCompletePack(){
  3.     int[] weight = {1, 3, 4};
  4.     int[] value = {15, 20, 30};
  5.     int bagWeight = 4;
  6.     int[] dp = new int[bagWeight + 1];
  7.     for (int i = 0; i < weight.length; i++){ // 遍历物品
  8.         for (int j = weight[i]; j <= bagWeight; j++){ // 遍历背包容量
  9.             dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
  10.         }
  11.     }
  12.     for (int maxValue : dp){
  13.         System.out.println(maxValue + "   ");
  14.     }
  15. }
  17. //先遍历背包，再遍历物品
  18. private static void testCompletePackAnotherWay(){
  19.     int[] weight = {1, 3, 4};
  20.     int[] value = {15, 20, 30};
  21.     int bagWeight = 4;
  22.     int[] dp = new int[bagWeight + 1];
  23.     for (int i = 1; i <= bagWeight; i++){ // 遍历背包容量
  24.         for (int j = 0; j < weight.length; j++){ // 遍历物品
  25.             if (i - weight[j] >= 0){
  26.                 dp[i] = Math.max(dp[i], dp[i - weight[j]] + value[j]);
  27.             }
  28.         }
  29.     }
  30.     for (int maxValue : dp){
  31.         System.out.println(maxValue + "   ");
  32.     }
  33. }

Python：

  1. # 先遍历物品，再遍历背包
  2. def test_complete_pack1():
  3.     weight = [1, 3, 4]
  4.     value = [15, 20, 30]
  5.     bag_weight = 4
  7.     dp = [0]*(bag_weight + 1)
  9.     for i in range(len(weight)):
  10.         for j in range(weight[i], bag_weight + 1):
  11.             dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
  13.     print(dp[bag_weight])
  15. # 先遍历背包，再遍历物品
  16. def test_complete_pack2():
  17.     weight = [1, 3, 4]
  18.     value = [15, 20, 30]
  19.     bag_weight = 4
  21.     dp = [0]*(bag_weight + 1)
  23.     for j in range(bag_weight + 1):
  24.         for i in range(len(weight)):
  25.             if j >= weight[i]: dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
  27.     print(dp[bag_weight])
  30. if __name__ == '__main__':
  31.     test_complete_pack1()
  32.     test_complete_pack2()

Go：

  2. // test_CompletePack1 先遍历物品, 在遍历背包
  3. func test_CompletePack1(weight, value []int, bagWeight int) int {
  4.     // 定义dp数组 和初始化
  5.     dp := make([]int, bagWeight+1)
  6.     // 遍历顺序
  7.     for i := 0; i < len(weight); i++ {
  8.         // 正序会多次添加 value[i]
  9.         for j := weight[i]; j <= bagWeight; j++ {
  10.             // 推导公式
  11.             dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
  12.             // debug
  13.             //fmt.Println(dp)
  14.         }
  15.     }
  16.     return dp[bagWeight]
  17. }
  19. // test_CompletePack2 先遍历背包, 在遍历物品
  20. func test_CompletePack2(weight, value []int, bagWeight int) int {
  21.     // 定义dp数组 和初始化
  22.     dp := make([]int, bagWeight+1)
  23.     // 遍历顺序
  24.     // j从0 开始
  25.     for j := 0; j <= bagWeight; j++ {
  26.         for i := 0; i < len(weight); i++ {
  27.             if j >= weight[i] {
  28.                 // 推导公式
  29.                 dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
  30.             }
  31.             // debug
  32.             //fmt.Println(dp)
  33.         }
  34.     }
  35.     return dp[bagWeight]
  36. }
  38. func max(a, b int) int {
  39.     if a > b {
  40.         return a
  41.     }
  42.     return b
  43. }
  45. func main() {
  46.     weight := []int{1, 3, 4}
  47.     price := []int{15, 20, 30}
  48.     fmt.Println(test_CompletePack1(weight, price, 4))
  49.     fmt.Println(test_CompletePack2(weight, price, 4))
  50. }

Javascript:

  1. // 先遍历物品，再遍历背包容量
  2. function test_completePack1() {
  3.     let weight = [1, 3, 5]
  4.     let value = [15, 20, 30]
  5.     let bagWeight = 4 
  6.     let dp = new Array(bagWeight + 1).fill(0)
  7.     for(let i = 0; i <= weight.length; i++) {
  8.         for(let j = weight[i]; j <= bagWeight; j++) {
  9.             dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])
  10.         }
  11.     }
  12.     console.log(dp)
  13. }
  15. // 先遍历背包容量，再遍历物品
  16. function test_completePack2() {
  17.     let weight = [1, 3, 5]
  18.     let value = [15, 20, 30]
  19.     let bagWeight = 4 
  20.     let dp = new Array(bagWeight + 1).fill(0)
  21.     for(let j = 0; j <= bagWeight; j++) {
  22.         for(let i = 0; i < weight.length; i++) {
  23.             if (j >= weight[i]) {
  24.                 dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])
  25.             }
  26.         }
  27.     }
  28.     console.log(2, dp);
  29. }

背包问题理论基础完全背包 - 图5