代码随想录算法训练营第四十四天 完全背包 、零钱兑换 II 、组合总和 Ⅳ

代码随想录算法训练营第四十四天 | 完全背包 、零钱兑换 II 、组合总和 Ⅳ

完全背包

题���链接：题目页面 (kamacoder.com)

（）

解释一、01背包 一维 ：为什么要倒序遍历背包？

首先要明白二维数组的递推过程，然后才能看懂二维变一维的过程。

（）

假设目前有背包容量为10，可以装的最大价值， 记为g(10)。

即将进来的物品重量为6。价值为9。

那么此时可以选择装该物品或者不装该物品。

如果不装该物品，显然背包容量无变化，这里对应二维数组，其实就是取该格子上方的格子复制下来，就是所说的滚动下来，直接g【10】 = g【10】，这两个g【10】要搞清楚，右边的g【10】是上一轮记录的，也就是对应二维数组里上一层的值，而左边是新的g【10】，也就是对应二维数组里下一层的值。

如果装该物品，则背包容量= g(10-6) = g(4) + 9 ，也就是 g(10) = g(4) + 6 ,这里的6显然就是新进来的物品的价值，g(10)就是新记录的，对应二维数组里下一层的值，而这里的g(4)是对应二维数组里上一层的值，通俗的来讲：你要找到上一层也就是上一状态下 背包容量为4时的能装的最大价值，用它来更新下一层的这一状态，也就是加入了价值为9的物品的新状态。

这时候如果是正序遍历会怎么样？ g(10) = g(4) + 6 ，这个式子里的g(4)就不再是上一层的了，因为你是正序啊，g(4) 比g(10)提前更新，那么此时程序已经没法读取到上一层的g(4)了，新更新的下一层的g(4)覆盖掉了，这里也就是为啥有题解说一件物品被拿了两次的原因。

解释二、01背包到底先遍历物品还是先遍历背包呢？

其实在二维的时候，即使是先遍历背包重量，再遍历物品重量，你真的画图的时候会发现，永远的数据来源，依旧还是max(不放，放）= max(正上方的值，左上角的值)。

那你在一维的时候，如果先遍历背包容量的话:

如果你还是从左到右地遍历背包容量：一样会造成重复添加；

如果你从右到左地遍历背包容量：相当于你的计算顺序是先竖着写完第四列，再竖着写完第三列，再竖着写完第二列。。。但你写第四列的时候，第三列全部都是空的，左边是没有数据的，你永远只在累加正上方的数。而如果你是先遍历物品再遍历背包，你的填空顺序是，先写第一行（从右往左写），再写第二行的时候，你的左边是有数字的。。。

那你可能想问，我能不能做一个竖着的表格更新呢？其实没有帮助的，你只要先一股脑地竖着算，你永远没法利用起左边格子的数字——无法利用之前格子的数，那就不是动态规划了

解释三、为什么完全背包可以颠倒物品和背包的遍历顺序？

请想像一下 01背包的二维dp数组图像 和 完全背包的二维dp数组图像

01背包 的二维数组dp[i] [j]只取决于其左上角的值，所以 使用二维数组时可以从对物品和背包数组进行正序遍历，且先物品还是先背包可以颠倒

01背包的一维数组dp[j] 因为

背包必须要倒序遍历（参考上面解释一、01背包 一维 ：为什么要倒序遍历背包）

↓

如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品（解释二）

↓

所以要先物品后背包

完全背包其dp[j]完全取决于

// 先遍历物品再遍历背包import java.util.*;public class Main {    public static void main (String[] args) {        Scanner sc = new Scanner(System.in);        int N = sc.nextInt();        int V = sc.nextInt();        int[] weights = new int[N];        int[] values = new int[N];        for(int i = 0; i  这样得到的是 组合        先遍历背包，背包容量的每一个值，都是经过 1 和 5 的计算，包含了{1, 5} 和 {5, 1}两种情况        -> 这样得到的是 排列         不理解的话可以打印dp数组来看看         */        for(int i = 0; i