完全背包问题

完全背包问题和0-1背包问题的差别为：完全背包物品的数量没有限制，而0-1背包每个物品的数量为1个。

//先遍历物品，再遍历背包
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++){
     // 遍历背包容量
            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 + " ");
    }
}

leetcode上的变形题，不是这种纯完全背包的问题了。
分为两种：
1、组合问题，组合问题不讲究先后顺序，{1,5}和{5,1}是一样的
2、排列问题，排列问题要注意先后顺序，{1,5}和{5,1}是两个答案

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

典型的组合问题，不要求顺序，{1，2，2} 和{2，1，2}是一样的，组成总金额为5的数，所需一枚一块和两枚两块的，不要求顺序，所以先遍历遍历物品，再遍历背包

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];

这道题求排列数，从测试用例可看出，所以先遍历背包，再遍历物品

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-nums[j]];
            }
        }
        return dp[target];

    }