动态规划1.2--背包问题之完全背包

本文参考:动态规划：关于完全背包，你该了解这些！

1、问题定义

上一节，我们介绍了0-1背包，每种物品只有一件时，背包能装的最大价值。本节，我们讨论当每种物品的数量不限（也就是可以放入背包多次）时，背包能装的最大价值。

2、遍历顺序

0-1背包和完全背包唯一不同就是体现在遍历顺序上，所以本文就不去做动规五部曲了，我们直接针对遍历顺序经行分析！
首先，我们回顾一下，用滚动数组实现的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数组的两个for遍历的先后循序是可以颠倒了，一位dp数组的两个for循环先后循序一定是先遍历物品，再遍历背包容量。

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

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

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

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

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

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

参考:动态规划：关于完全背包，你该了解这些！