Knapsack problem - Java solution with thinking process O(nm) Time and O(m) Space


  • 55

    This is a classic knapsack problem. Honestly, I'm not good at knapsack problem, it's really tough for me.

    dp[i][j] : the number of combinations to make up amount j by using the first i types of coins
    State transition:

    1. not using the ith coin, only using the first i-1 coins to make up amount j, then we have dp[i-1][j] ways.
    2. using the ith coin, since we can use unlimited same coin, we need to know how many way to make up amount j - coins[i] by using first i coins(including ith), which is dp[i][j-coins[i]]

    Initialization: dp[i][0] = 1

    Once you figure out all these, it's easy to write out the code:

        public int change(int amount, int[] coins) {
            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++) {
                    dp[i][j] = dp[i-1][j] + (j >= coins[i-1] ? dp[i][j-coins[i-1]] : 0);
                }
            }
            return dp[coins.length][amount];
        }
    

    Now we can see that dp[i][j] only rely on dp[i-1][j] and dp[i][j-coins[i]], then we can optimize the space by only using one-dimension array.

        public int change(int amount, int[] coins) {
            int[] dp = new int[amount + 1];
            dp[0] = 1;
            for (int coin : coins) {
                for (int i = coin; i <= amount; i++) {
                    dp[i] += dp[i-coin];
                }
            }
            return dp[amount];
        }
    

  • 0
    P

    In knapsack every item has two attributes (i.e weight and a value) but in this problem every coin has just 1 attribute the value. How can you compare it to knapsack? Perhaps I did not understand your thought process correctly. i understand that every time you have to choose between whether to pick this coin or not. But still when I think about the original coin change problem i get confused. Could you please elaborate ?


  • 0
    F

    for (int i = coin;...) the initial of i is really beautiful. Thanks!


  • 0
    P

    Still have difficulty to understand why the solution is the sum of case using ith coin and case not using ith coin and Why this is sufficient. anyone could share any illustration to help?


  • 3
    M

    Hi all!

    Can you please explain the difference between this solution - O(m) space complexity - and the following one:

    https://discuss.leetcode.com/topic/52302/1ms-java-dp-solution-with-detailed-explanation/

    I am interested in the way this solution does not count the same combination more than once while the other does.

    Thanks!


  • 7
    Y

    The difference is that if you update dp while:

    • increasing i then the previous partial result dp[i - coin] is the result that has considered coin already
    • decreasing i then the previous partial result dp[i - coin] is the result that has not considered coin yet
    /** 
     * @return number of ways to make sum s using repeated coins
     */
    public static int coinrep(int[] coins, int s) {
        int[] dp = new int[s + 1]; 
        dp[0] = 1;          
        for (int coin : coins)      
            for (int i = coin; i <= s; i++)         
                dp[i] += dp[i - coin];                                  
        return dp[s];
    }                                       
                                                
    /**
     * @return number of ways to make sum s using non-repeated coins
     */
    public static int coinnonrep(int[] coins, int s) {
        int[] dp = new int[s + 1];
        dp[0] = 1;  
        for (int coin : coins)
            for (int i = s; i >= coin; i--)
                dp[i] += dp[i - coin];              
        return dp[s];                                                   
    } 
    

  • 0
    J
    This post is deleted!

  • 0
    L

    A question on why we have Initialization: dp[i][0] = 1, as described by tankztc, dp[i][j] represent the number of combinations to make up amount j by the first i types of coins, so dp[i][0] should represent the number of combinations to make up 0 by the first i types of coins, the number of combinations is 0, so dp[i][0] = 0 right ? Why initialize as 1 ?

    Have a tricky perspective: use no coins (auto deduct result as amount = 0) is actually 1 method (or understand as use no coins is also a kind of combination) ? Not sure if any better perspective than this explain ?


  • 0
    G

    @lampard08 I do not think OP's initialization is correct. The correct initilization should be: dp[0][0] = 1 and dp[i][0] = 0 and dp[0][i] = 0


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.