代码随想录第三十七天（完全背包问题）|完全背包|零钱兑换 II|组合总和 Ⅳ

完全背包问题

完全背包问题和01背包的区别就在于每一个物品可取的次数，01背包每个物品只能取一次，完全背包每个物品能取无数次。

而01背包为了保证每个物品只取一次，在遍历背包的时候需要倒序遍历，这样才能保证之前的状态都是初始状态，没有添加过物品，利用之前的状态时就不会将同一个物品进行重复添加。

在完全背包中，就需要每个物品能取多次，于是解除遍历背包时的倒序限制就行。

import java.util.*;
public class Main{
    public static void main (String[] args) {
        Scanner sc=new Scanner(System.in);
        int M=sc.nextInt();
        int N=sc.nextInt();
        int[] weight=new int[M];
        int[] value=new int[M];
        
        int bagsize=N;
        for(int i=0;i<M;i++){
            weight[i]=sc.nextInt();
            value[i]=sc.nextInt();
        }
        maxValue(weight,value,bagsize);
    }
    
    public static void maxValue(int[] weight,int[] value,int bagsize){
        int[] dp=new int[bagsize+1];
        for(int i=0;i<weight.length;i++){
            for(int j=weight[i];j<bagsize+1;j++){
                dp[j]=Math.max(dp[j],dp[j-weight[i]]+value[i]);
            }
        }
        System.out.println(dp[bagsize]);
    }
}

在完全背包中，在求装满指定容量背包的组合总数的时候，遍历顺序非常重要，只求组合总数的话，先遍历物品，后遍历背包，因为先遍历物品的话，每次都会将前一个物品先添加进去，只会出现{1,2}这样的组合，不会出现{2,1}的组合。因为当前物品层依赖上一个物品层传递下来的状态，上一个物品层，就只会又上一个物品层和其之前的物品层的组合。不会有之后物品层的值放入组合中。

而将遍历顺序颠倒，先遍历背包，后遍历物品，以物品{1,2,3}为例，装满容量为4的背包，y轴为物品，x轴为背包。

当背包容量为3，假如已取物品1，也就是先放入重量为2的物品，剩余只能取重量为1的组合了，就出现了{2,1}，而假如已取的是物品0，也就是先放入重量为1的物品，剩余只能取重量为2的组合，因为在上一个状态遍历了物品1，已经有了重量2的组合，就出现了{1,2}和{1,1,1}的组合了。

零钱兑换 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+1;j++){
                dp[j]+=dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
}

组合总和 Ⅳ

讲究顺序

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp=new int[target+1];
        dp[0]=1;
        for(int j=1;j<target+1;j++){
            for(int i=0;i<nums.length;i++){
                if(j>=nums[i]){
                    dp[j]+=dp[j-nums[i]];
                }
            }
        }
        return dp[target];
    }
}