LetCode 0-1 Knapsack 가방 문제 & 관련 문제

내 Letcode 질문에 대한 해답은 코드가 Github로 이동합니다.https://github.com/chenxiangcyr/leetcode-answers
Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W . You cannot break an item, either pick the complete item, or don’t pick it (0-1 property).
코드는 다음과 같습니다. 귀속과 비귀속 알고리즘을 포함합니다.시간 복잡성O(n * W)

class Knapsack {

    // Returns the maximum value that can be put in a knapsack of capacity W
    static int knapSackRecursive(int W, int wt[], int val[], int n) {
        // Base Case
        if (n == 0 || W == 0)
            return 0;

        // If weight of the nth item is more than Knapsack capacity W, then
        // this item cannot be included in the optimal solution
        if (wt[n - 1] > W)
            return knapSackRecursive(W, wt, val, n - 1);

        // Return the maximum of two cases:
        // (1) nth item included
        // (2) not included
        else
            return Math.max(
                    val[n - 1]
                            + knapSackRecursive(W - wt[n - 1], wt, val, n - 1),
                    knapSackRecursive(W, wt, val, n - 1));
    }

    // Returns the maximum value that can be put in a knapsack of capacity W
    static int knapSackIterative(int W, int wt[], int val[], int n) {

        // dp[i][j] stores the maximum value when there are i element and the
        // knapstack is j
        int[][] dp = new int[n + 1][W + 1];
        dp[0][0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= W; j++) {
                if (wt[i - 1] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    /*
                     * case1:    i   ，    val[i] case2:     i   
                     */
                    int val1 = val[i - 1] + dp[i - 1][j - wt[i - 1]];
                    int val2 = dp[i - 1][j];

                    dp[i][j] = Math.max(val1, val2);
                }
            }
        }

        return dp[n][W];
    }

    // Driver program to test above function
    public static void main(String args[]) {
        int val[] = new int[] { 60, 100, 120 };
        int wt[] = new int[] { 10, 20, 30 };
        int W = 51;
        int n = val.length;
        System.out.println(knapSackIterative(W, wt, val, n));
    }
}

LetCode 제목:518.Coin Change 2 You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

class Solution {
    public int change(int amount, int[] coins) {
        /*
        dp[i][j]      i     j      
        */
        int[][] dp = new int[coins.length + 1][amount + 1];
        dp[0][0] = 1;
        
        for(int i = 1; i <= coins.length; i++) {
            dp[i][0] = 1;
            
            for(int j = 1; j <= amount; j++) {
                
                int coin = coins[i - 1];
                /*
                case1:    i   
                case2:     i   
                */
                dp[i][j] = dp[i - 1][j] + (j >= coin ? dp[i][j - coin] : 0);
                
            }
        }
        
        return dp[coins.length][amount];
    }
}

LetCode 제목:416.Partition Equal Subset Sum Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal. Note: Each of the array element will not exceed 100. The array size will not exceed 200.
Example 1: Input: [1, 5, 11, 5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11].

class Solution {
    public boolean canPartition(int[] nums) {
        
        if(nums == null || nums.length < 2) return false;
        
        int sum = 0;
        for(int i : nums) {
            sum = sum + i;
        }
        
        // odd
        if(sum % 2 == 1) return false;
        
        sum = sum /2;
        
        // 0-1    
        int n = nums.length;
        
        // dp[i][j]       i         j     
        boolean[][] dp = new boolean[n + 1][sum + 1];
        
        for (int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i], false);
        }

        dp[0][0] = true;

        //    
        for (int i = 1; i < n + 1; i++) {
            dp[i][0] = true;
        }
        
        //    
        for (int j = 1; j < sum + 1; j++) {
            dp[0][j] = false;
        }

        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < sum + 1; j++) {
                
                if (j >= nums[i - 1]) {
                    dp[i][j] = (dp[i - 1][j] || dp[i - 1][j - nums[i - 1]]);
                }
                
                else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[n][sum];
    }
}

참조: Dynamic Programming | Set 10 (0-1 Knapsack Problem)