Complete knapsack problem

Complete knapsack problem and 0-1 The difference between knapsack problems is ： There is no limit to the number of complete backpack items , and 0-1 The quantity of each item in the backpack is 1 individual .

// Go through the items first , And then traverse the backpack 
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++){
     //  Traverse the items 
        for (int j = weight[i]; j <= bagWeight; j++){
     //  Traverse the backpack capacity 
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    for (int maxValue : dp){
    
        System.out.println(maxValue + " ");
    }
}

// Go through the backpack first , Then traverse the items 
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++){
     //  Traverse the backpack capacity 
        for (int j = 0; j < weight.length; j++){
     //  Traverse the items 
            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 Deformation problem on , It is not the problem of this kind of pure and complete backpack .
Divided into two ：
1、 Combination question , Combinatorial problems do not pay attention to order ,{1,5} and {5,1} It's the same
2、 The problem of permutation , You should pay attention to the order of arrangement ,{1,5} and {5,1} There are two answers

If you find the combination number, it's the outer layer for Loop through items , Inner layer for Traverse the backpack .

If you find the permutation number, it's the outer layer for Traverse the backpack , Inner layer for Loop through items .

Typical combinatorial problems , Order is not required ,{1,2,2} and {2,1,2} It's the same , The total amount of the composition is 5 Number of numbers , One piece and two pieces are required , Order is not required , So go through the items first , And then traverse the backpack

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

This problem is to find the number of permutations , It can be seen from the test cases , So go through the backpack first , Then traverse the items

public int combinationSum4(int[] nums, int target) {
    
        int[] dp = new int[target+1];
        dp[0] = 1;
        // Go through the backpack first , Then traverse the items 
        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];

    }