0/1 Knapsack | Top Down➡️Bottom Up | 4 Solutions | Readable C++ Code🔥
vHiren
5776
Dynamic ProgrammingKnapsack Problem0-1 KnapsackInterview

You are given weights and values of N items, put these items in a knapsack of the given capacity to get the maximum total value in the knapsack. Note that we have only one quantity of each item.
In other words, given two integer arrays values[0..N-1] and weights[0..N-1] which represent values and weights associated with N items respectively. Also given an integer "capacity" which represents knapsack capacity, find out the maximum value subset of values[] such that sum of the weights of this subset is smaller than or equal to the given capacity. You cannot break an item, either pick the complete item or dont pick it (0-1 property).

N = 3
capacity = 4
values[] = {1,2,3}
weights[] = {4,5,1}
Output: 3
Explanation: Choose the last item that weighs 1 unit and holds a value of 3.

Note: Hey There! Just Take A Look At The Code And Comments Within It. You'll Get It.
Note: Time Complexity And Auxiliary Space Is Mentioned With The Code.
Note: If You Have Any Kind Of Doubt, Just Comment And I'll Be There For You.

Approach 1 : Using Top Down DP (Recursion To Memoization)

class TopDown {
    int n;
    
    // O(2^N) & O(N)
    int solveWithoutMemo(vector<int>& nums, vector<int>& cost, int i, int k) {
        if(i == n || k == 0)
            return 0;
        
        int currSkip = solveWithoutMemo(nums, cost, i + 1, k);
        int currTake = cost[i] <= k 
                        ? nums[i] + solveWithoutMemo(nums, cost, i + 1, k - cost[i])
                        : 0;
                       
        return max(currSkip, currTake);
    }
    
    // O(N*C) & O(N*C) : Where C = capacity
    int solveWithMemo(vector<vector<int>>& dp, vector<int>& nums, vector<int>& cost, int i, int k) {
        if(i == n || k == 0)
            return 0;
            
        if(dp[i][k] != -1)
            return dp[i][k];
        
        int currSkip = solveWithMemo(dp, nums, cost, i + 1, k);
        int currTake = cost[i] <= k 
                        ? nums[i] + solveWithMemo(dp, nums, cost, i + 1, k - cost[i])
                        : 0;
                       
        return dp[i][k] = max(currSkip, currTake);
    }
    
    // O(N*N*C) & O(N*C) : Where C = capacity
    int solveWithMemoLoop(vector<vector<int>>& dp, vector<int>& nums, vector<int>& cost, int start, int k) {
        if(start == n || k == 0)
            return 0;
            
        if(dp[start][k] != -1)
            return dp[start][k];
        
        int maxSum = 0;
        
        for(int i = start; i < n; ++i) {
            int currTake = cost[i] <= k 
                            ? nums[i] + solveWithMemoLoop(dp, nums, cost, i + 1, k - cost[i])
                            : 0;
            maxSum = max(maxSum, currTake);
        }
            
        return dp[start][k] = maxSum;
    }
    
public:
    int knapsack(int capacity, vector<int>& values, vector<int>& weights) {
        n = values.size();
        vector<vector<int>> dp(n, vector<int>(capacity + 1, -1));
        return solveWithMemo(dp, values, weights, 0, capacity);
    }
};

Approach 2 : Using Bottom Up DP (2D + 1D Tabulation)

class BottomUp {
    int n;
    
    // O(N*C) & O(N*C) : Where C = capacity
    int solveBy2DTable(const vector<int>& nums, const vector<int>& cost, int given_k) {
        vector<vector<int>> dp(n + 1, vector<int>(given_k + 1, -1));
        
        for(int k = 0; k <= given_k; ++k)
            dp[n][k] = 0;
        
        for(int i = 0; i <= n; ++i)
            dp[i][0] = 0;
        
        for(int i = n - 1; i >= 0; --i) {
            for(int k  = 1; k <= given_k; ++k) {
                int currSkip = dp[i + 1][k];
                int currTake = cost[i] <= k 
                                ? nums[i] + dp[i + 1][k - cost[i]]
                                : 0;
                dp[i][k] = max(currSkip, currTake);  
            }
        }
        
        return dp[0][given_k];
    }
    
    // O(N*C) & O(N*C) : Where C = capacity
    int solveBy2DEnhanced(const vector<int>& nums, const vector<int>& cost, int given_k) {
        vector<vector<int>> dp(n + 1, vector<int>(given_k + 1, 0));
        
        for(int i = n - 1; i >= 0; --i) {
            for(int k  = 1; k <= given_k; ++k) {
                int currSkip = dp[i + 1][k];
                int currTake = cost[i] <= k 
                                ? nums[i] + dp[i + 1][k - cost[i]]
                                : 0;
                dp[i][k] = max(currSkip, currTake);  
            }
        }
        
        return dp[0][given_k];
    }
    
    // O(N*C) & O(C) : Where C = capacity
    int solveBy1DTable(const vector<int>& nums, const vector<int>& cost, int given_k) {
        vector<int> nextRow(given_k + 1, 0), idealRow(given_k + 1, 0); 
        
        for(int i = n - 1; i >= 0; --i) {
            for(int k  = 1; k <= given_k; ++k) {
                int currSkip = nextRow[k];
                int currTake = cost[i] <= k 
                                ? nums[i] + nextRow[k - cost[i]]
                                : 0;
                idealRow[k] = max(currSkip, currTake);  
            }
            swap(nextRow, idealRow);
        }
        
        return nextRow[given_k];
    }
    
public:
    int knapsack(int capacity, vector<int>& values, vector<int>& weights) {
        n = values.size();
        vector<vector<int>> dp(n, vector<int>(capacity + 1, -1));
        return solveBy1DTable(values, weights, capacity);
    }
};

𝗨𝗣𝗩𝗢𝗧𝗘 𝗜𝗙 𝗬𝗢𝗨 𝗟𝗜𝗞𝗘 𝗧𝗛𝗘 𝗦𝗢𝗟𝗨𝗧𝗜𝗢𝗡 👍

Note: This solutions are created by myself :)

Comments (3)