完全背包

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

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

直接从递推公式本身入手，之前的0-1背包，推导下一行需要用到上一行的数据，因此把上一行copy到这一行，然后在这一行的基础上进行运算，在遍历的时候，我们是遍历一个，修改一个，如果后面的还要用被修改之前的数据，就出bug了，因此遍历的时候要保证修改了的后面不会再用到，而根据递推公式，只和左边的以及自己本身有关，因此从右向左递推可以保证后面的数据还是基于未被修改的数据计算得到的。而对于完全背包，用的本来就是这一行已经被修改过的数据，所以必须从左向右，先得到修改后的数据，才可以继续往后遍历

二维dp更好理解。所谓正序遍历就是把之前的【i-1】都改成了【i】，也就是在考虑要不要加物品i的时候，可以是已经加过物品i的，而不一定是只加过前i-1个。也就是可以重复加。二维数组开始讲比较好理解，二维数组解法01背包是继承上层左侧状态，完全背包是继承本层左侧状态。所以压缩成一维数组后是正向遍历

为什么一维的dp里面，完全背包是正序，01背包是倒序？而且交换物品和容量也无所谓

因为01背包的dp里面，在递推的过程中dp【j】需要的是上一层的dp【j - weight【i】】。如果正序的话，dp【j - weight【i】】就被更新成了前i个物品，容量为j - weight【i】的最大值，那么dp【j】就没办法推了，因为前面已经包括了第i个物品（如果更新了）。
完全背包里面需要的则是j - weight【i】容量里面的最大值，不需要考虑到底是前几个物品组成的最大值。

所以在递推过程中，完全背包的一维dp的值并不完全和二维dp一样，但是最后的结果是一样的。
这是和01背包不同的点
换个例子模拟一下过程，视频中的例子看不出来什么
weight = {1,2,3,4}
value = {10, 21,30,43}
bagWeight = 5

01背包和完全背包的区别：

01背包：

完全背包（继承上一层状态）：

//先遍历物品，再遍历背包
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++){ // 遍历背包容量,这里要从当前放入的这个物品weight[i]开始，前面的容量太小反正也放不进去
            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 + "   ");
    }
}

518. 零钱兑换 II

中等
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。

遍历顺序（组合与排列）

网友①：
dp【j】=dp【j-coins【i】】其区别就在于i
第一、先遍历物品再遍历背包容量，对于特定的物品，遍历一遍背包容量，将物品尽可能放入背包。然后再遍历第二个物品时，只会放第二个物品，故物品之间存在放入顺序，按物品序号递增排列，代表组合。
第二、先遍历背包容量再遍历物品，对于每一背包容量j，都会遍历一遍物品coins【i】（0<=i<coins.size()），将对应的dp【j-coins【i】】。说明物品排列无序，代表排列

网友②：
遍历顺序（组合与排列）
dp【j】=dp【j-coins【i】】其区别就在于i
第一、先遍历物品再遍历背包容量，对于特定的物品，遍历一遍背包容量，将物品尽可能放入背包。然后再遍历第二个物品时，只会放第二个物品，故物品之间存在放入顺序，按物品序号递增排列，代表组合。
第二、先遍历背包容量再遍历物品，对于每一背包容量j，都会遍历一遍物品coins【i】（0<=i<coins.size()），将对应的dp【j-coins【i】】。说明物品排列无序，代表排列
网友③：
产生排列的原因：

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1]; // dp[j]：凑成总金额j的货币组合数为dp[j]
        dp[0] = 1;

        for (int i = 0; i < coins.length; i++) { //遍历物品
            for (int j = coins[i]; j <= amount; j++) { // 遍历背包
                // 求装满背包有几种方法，公式都是：dp[j] += dp[j - nums[i]];
                dp[j] = dp[j] + dp[j - coins[i]];
            }
        }

        return dp[amount];
    }
}

二维数组版本

377. 组合总和 Ⅳ

中等
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

难点：

本题题目描述说是求组合，但又说是可以元素相同顺序不同的组合算两个组合，其实就是求排列！
这里用上一题来举个例子说明为何是排列：

// 完全背包排列问题
class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;

        for (int i = 0; i <= target; i++) { // 先遍历背包
            for (int j = 0; j < nums.length; j++) {  // 遍历物品
                if (i >= nums[j]) { // 如果能装进去
                    dp[i] = dp[i] + dp[i - nums[j]];
                }
            }
        }

        return dp[target];
    }
}