训练营四十四天 | ● 完全背包● 518. 零钱兑换 II ● 377. 组合总和 Ⅳ

先物品再背包和先背包再物品都行，背包正序遍历，可以重复选取

先物品再背包是组合，不讲究各个物品的不同顺序，因为先顺序遍历物品，所以物品只有一种排序，即组合

先背包再物品是排序，物品可以有不同顺序

https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85.html 

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[] weight = new int[N];
        int[] value = new int[N];
        for(int i = 0; i < N; i++) {
            weight[i] = sc.nextInt();
            value[i] = sc.nextInt();
        }
        int[] dp = new int[V+1];//一维数组
        for(int i = 0; i < N; i++) {
            for(int j = weight[i]; j <= V; j++) {//正序遍历
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        System.out.println(dp[V]); 
    }  
}

 518. 零钱兑换 II  视频讲解：

代码随想录

完全背包 方法数 组合

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;//初始化
        for(int i = 0; i < coins.length; i++) {//物品
            for(int j = coins[i]; j <= amount; j++) {//背包正序
                dp[j] += dp[j - coins[i]];//递推公式
            }
        }
        return dp[amount];
    }
}

 377. 组合总和 Ⅳ  视频讲解：

代码随想录

完全背包 方法数 排序

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;//初始化
        for(int j = 0; j <= target; j++) {//背包正序
            for(int i = 0; i < nums.length; i++) {//物品
                if(j >= nums[i]) {
                    dp[j] += dp[j - nums[i]]; 
                }
            }
        }
        return dp[target];
    }
}