训练营四十四天 | ● 完全背包● 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];
    }
}