Knapsack Problems

Round 1

Questions: Problem: Given N items, each with weight w[i] and value v[i], and a bag of capacity W, find the maximum value you can obtain without limiting item selection.

Perfect Squares

Find the minimum number of perfect squares that sum up to n.
Leetcode Problem Link

class Solution {
public:
    int numSquares(int n) {
        if (n <= 0) return 0;
        vector<int> dp(n+1,INT_MAX); // n is the capacity/target 
        // dp[i] represent the number of perfect squre for sum i 
        dp[0]=0;

        for(int i=1 ; i<=n ; i++){          // Iterate over target sum
            for(int j=1 ; j*j <= i ; j++){   // Try all perfect squares <= i basially items that theif 
                dp[i] = min(dp[i],dp[i-j*j]+1); // include this one + previous count before this perfect squre
            }
        }
        return dp[n];
    }
};

/* The Perfect Squares is Unbounded Knapsack problem because: You need to reach a target sum (n) using a given set of numbers (perfect squares like 1, 4, 9, 16,...). You can reuse numbers, meaning you can take a perfect square multiple times (just like unbounded knapsack).

Items -> Items with weights and values -> Perfect squares (1, 4, 9, ...) Capacity -> Knapsack weight limit W -> Target sum n Decision -> Pick an item multiple times to maximize value -> Pick squares multiple times to minimize count DP Formula -> dp[i] = max(dp[i], dp[i - weight] + value) -> dp[i] = min(dp[i], dp[i - square] + 1) */

Integer Break

Given an integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.
Leetcode Problem Link

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1, 0);
        dp[1] = 1; // Base case

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = max(dp[i], max(j, dp[j]) * max(i - j, dp[i - j]));
            }
        }
        return dp[n];
    }
};

/* Items: -> A set of items with weights and values. -> Numbers from 1 to n, which can be used multiple times. Capacity: -> The maximum weight the knapsack can hold -> Target sum (n) that needs to be split. Decision: -> Whether to pick an item multiple times to maximize value. -> Break n into numbers to maximize the product. DP Formula: dp[i] = max(dp[i], dp[i - weight] + value). -> dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j])). */

Coin Change 2

Given an array of coins and an amount, find the number of ways to make up the amount using the coins.
Leetcode Problem Link

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        
        vector<unsigned long long int> dp(amount+1,0);
        dp[0]=1;                                // There's 1 way to make 0 (by taking no coins)
        for(auto coin:coins){                   // Iterate over each coin
            for(auto i=1;i<=amount;i++){        // Iterate over each amount
                if(coin<=i)                     // coin should be less than target amount 
                    dp[i]=dp[i]+dp[i-coin];     // Include the current coin + no of ways before this coin
            }
        }
        return dp[amount];                      // no of ways to reach amount
    }
};

Coin Change 1

Given an array of coins and an amount, find the minimum number of coins needed to make up the amount.
Leetcode Problem Link

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        
        vector<unsigned long long int> dp(amount+1, INT_MAX);          
        // dp[i] represents the fewest number of coins to make up the amount i
        dp[0] = 0;  // There is 0 min ways to make 0
        
        for (int i = 1; i <= amount; i++) {  // Iterate over all the amount 
            for (auto coin : coins) {        // Iterate over all the coins
                if (coin <= i) {             // if count is less than i otherwise we can't fit the coin
                    dp[i] = min(dp[i], dp[i-coin]+1);  
                    // last no of coins used at i vs (no of coins at i- coin + one more coin at i )
                }
            }
        }
        
        return dp[amount] == INT_MAX ? -1 : dp[amount]; // if not infi we can reach the sum 
    }
};