0 and 1 Knapsack

Why a Greedy Solution will not work:

As the question is asking for maximum value, the first approach that comes to our mind is greedy. A greedy solution will fail in this problem because there is no ‘uniformity’ in data. While selecting a local better choice we may choose an item that will in long term give less value. So we will solve this problem using recursion.

Steps to form the recursive solution:

Express the problem in terms of indexes:We are given ‘n’ items. Their weight is represented by the ‘wt’ array and value by the ‘val’ array. So clearly one parameter will be ‘ind’, i.e index up to which the array items are being considered. There is one more parameter 'W', the capacity of the knapsack to decide whether we can pick an array item or not in the knapsack.
So initially, we need to find f(n-1, W) where W is the overall capacity given to us. f(n-1, W) gives the maximum value of items that we can get from index 0 to n-1 with capacity W of the knapsack.
Try out all possible choices at a given index:We need to generate all the subsequences. We will use the pick/non-pick technique. There will be two choices:

Exclude the current element from the subsequence: First try to find a subsequence without considering the current index item. If we exclude the current item, the capacity of the bag will not be affected and the value added will be 0 for the current item. So we will call the recursive function f(ind-1,W),

Include the current element in the subsequence: Try to find a subsequence by considering the current item to the knapsack. As we have included the item, the capacity of the knapsack will be updated to (W-wt[ind]) and the current item’s value (val[ind] will also be added to the further recursive call answer. We will make a recursive call to f(ind-1, W- wt[ind]).

Note: We will consider the current item in the subsequence only when the current element’s weight is less than or equal to the capacity ‘W’ of the knapsack, if it isn’t we will not be considering it.

f(ind, W){
    notTake = 0 + f(ind-1, W)
    take = INT_MIN
    if(wt[ind] <= W)
         take = val[ind] + f(ind-1, W-wt[ind])
}

Return the maximum of take and notTake: As we have to return the maximum amount of value, we will return the maximum of take and notTake as our answer.

f(ind, W){
    notTake = 0 + f(ind-1, W)
    take = INT_MIN
    if(wt[ind] <= W)
         take = val[ind] + f(ind-1, W-wt[ind])
    return max(take, notTake)
}

Base Case: If ind==0, it means we are at the first item, so in that case we will check whether this item’s weight is less than or equal to the current capacity W, if it is, we simply return its value (val[0]) else we return 0.

#include <bits/stdc++.h>
using namespace std;

class Solution{
private:
    // Function to solve 0/1 Knapsack problem using memoization
    int func(vector<int>& wt, vector<int>& val, int ind, int W) {
        /* Base case: If there are no items left
        or the knapsack has no capacity, return 0*/
        if (ind == 0 || W == 0) {
            return 0;
        }

        /* Calculate the maximum value by either
        excluding the current item or including it*/
        int notTaken = func(wt, val, ind - 1, W);
        
        int taken = 0;
        /* Check if the current item can be included
        without exceeding the knapsack's capacity*/
        if (wt[ind] <= W) {
            taken = val[ind] + func(wt, val, ind - 1, W - wt[ind]);
        }

        // Return the result 
        return max(notTaken, taken);
    }
public:  
    // Function to solve the 0/1 Knapsack problem
    int knapsack01(vector<int>& wt, vector<int>& val, int n, int W) {
        return func(wt, val, n - 1, W);
    }
};

int main() {
    vector<int> wt = {1, 2, 4, 5};
    vector<int> val = {5, 4, 8, 6};
    int W = 5;
    int n = wt.size();

    
    //Create an instance of Solution class
    Solution sol;
    
    // Call the function to find the minimum coins
    int result = sol.knapsack01(wt, val, n, W);
    
    // Output the result
    cout << "The Maximum value of items is " << result << endl;
    
    return 0; 
}

import java.util.*;

class Solution {
    // Function to solve 0/1 Knapsack problem using memoization
    private int func(int[] wt, int[] val, int ind, int W) {
        /* Base case: If there are no items left
        or the knapsack has no capacity, return 0 */
        if (ind == 0 || W == 0) {
            return 0;
        }

        /* Calculate the maximum value by either
        excluding the current item or including it */
        int notTaken = func(wt, val, ind - 1, W);
        
        int taken = 0;
        /* Check if the current item can be included
        without exceeding the knapsack's capacity */
        if (wt[ind] <= W) {
            taken = val[ind] + func(wt, val, ind - 1, W - wt[ind]);
        }

        // Return the result 
        return Math.max(notTaken, taken);
    }

    // Function to solve the 0/1 Knapsack problem
    public int knapsack01(int[] wt, int[] val, int n, int W) {
        return func(wt, val, n - 1, W);
    }

    public static void main(String[] args) {
        int[] wt = {1, 2, 4, 5};
        int[] val = {5, 4, 8, 6};
        int W = 5;
        int n = wt.length;

        // Create an instance of Solution class
        Solution sol = new Solution();

        // Call the function to find the maximum value
        int result = sol.knapsack01(wt, val, n, W);

        // Output the result
        System.out.println("The Maximum value of items is " + result);
    }
}
class Solution:
    # Function to solve 0/1 Knapsack problem using memoization
    def func(self, wt, val, ind, W):
        """ Base case: If there are no items left
        or the knapsack has no capacity, return 0 """
        if ind == 0 or W == 0:
            return 0

        """ Calculate the maximum value by either
        excluding the current item or including it """
        notTaken = self.func(wt, val, ind - 1, W)
        
        taken = 0
        """ Check if the current item can be included
        without exceeding the knapsack's capacity"""
        if wt[ind] <= W:
            taken = val[ind] + self.func(wt, val, ind - 1, W - wt[ind])

        # Return the result 
        return max(notTaken, taken)

    # Function to solve the 0/1 Knapsack problem
    def knapsack01(self, wt, val, n, W):
        return self.func(wt, val, n - 1, W)

wt = [1, 2, 4, 5]
val = [5, 4, 8, 6]
W = 5
n = len(wt)

# Create an instance of Solution class
sol = Solution()

# Call the function to find the maximum value
result = sol.knapsack01(wt, val, n, W)

# Output the result
print("The Maximum value of items is", result)
class Solution {
    // Function to solve 0/1 Knapsack problem using memoization
    func(wt, val, ind, W) {
        /* Base case: If there are no items left
        or the knapsack has no capacity, return 0 */
        if (ind === 0 || W === 0) {
            return 0;
        }

        /* Calculate the maximum value by either
        excluding the current item or including it */
        let notTaken = this.func(wt, val, ind - 1, W);
        
        let taken = 0;
        /* Check if the current item can be included
        without exceeding the knapsack's capacity */
        if (wt[ind] <= W) {
            taken = val[ind] + this.func(wt, val, ind - 1, W - wt[ind]);
        }

        // Store the result in the DP table and return
        return Math.max(notTaken, taken);
    }

    // Function to solve the 0/1 Knapsack problem
    knapsack01(wt, val, n, W) {
        return this.func(wt, val, n - 1, W);
    }
}

const wt = [1, 2, 4, 5];
const val = [5, 4, 8, 6];
const W = 5;
const n = wt.length;

// Create an instance of Solution class
const sol = new Solution();

// Call the function to find the maximum value
const result = sol.knapsack01(wt, val, n, W);

// Output the result
console.log("The Maximum value of items is " + result);

Complexity Analysis:

Time Complexity: O(2^N), Where N is size of the array. As there are 2 choices for each index.

Space Complexity:O(N), As we are using a recursion stack space of N.

If we draw the recursion tree, we will see that there are overlapping subproblems. Hence the DP approaches can be applied to the recursive solution.

In order to convert a recursive solution to memoization the following steps will be taken:

Declare a dp array of size [n][W+1]: As there are two changing parameters in the recursive solution, 'ind' and 'target'. The size of the input array is ‘N’, so the index will always lie between ‘0’ and ‘n-1’. The capacity can take any value between ‘0’ and ‘W’. Therefore 2D dp array(dp[n][W+1]) is needed.

The dp array stores the calculations of subproblems. Initialize dp array with -1, to indicate that no subproblem has been solved yet.

While encountering an overlapping subproblem: When we come across a subproblem, for which the dp array has value other than -1, it means we have found a subproblem which has been solved before hence it is an overlapping subproblem. No need to calculate it's value again just retrieve the value from dp array and return it.
Store the value of subproblem: Whenever, a subproblem is enocountered and it is not solved yet(the value at this index will be -1 in the dp array), store the calculated value of subproblem in the array.

#include <bits/stdc++.h>
using namespace std;

class Solution{
private:
    // Function to solve the 0/1 Knapsack problem with arrays
    int func(vector<int> &wt, vector<int> &val, int ind, int W, vector<vector<int>>& dp) {
        /* Base case: If there are no items left
        or the knapsack has no capacity, return 0 */
        if (ind < 0 || W == 0) {
            return 0;
        }

        /* If the result for this state is
        already calculated, return it */
        if (dp[ind][W] != -1) {
            return dp[ind][W];
        }

        /* Calculate the maximum value by either
        excluding the current item or including it */
        int notTaken = func(wt, val, ind - 1, W, dp);
        int taken = 0;

        /* Check if the current item can be included
        without exceeding the knapsack's capacity */
        if (wt[ind] <= W) {
            taken = val[ind] + func(wt, val, ind - 1, W - wt[ind], dp);
        }

        // Store the result in the DP table and return
        return dp[ind][W] = max(notTaken, taken);
    }

public:
    /* Function to return max value that
    can be put in knapsack of capacity W.*/
    int knapsack01(vector<int> wt, vector<int> val, int n, int W) { 
        // Initialize DP table with -1
        vector<vector<int>> dp(n, vector<int>(W + 1, -1));
        return func(wt, val, n - 1, W, dp);
    }
};
int main() {
    vector<int> wt = {1, 2, 4, 5};
    vector<int> val = {5, 4, 8, 6};
    int W = 5;
    int n = wt.size();
    
    //Create an instance of Solution class
    Solution sol;

    cout << "The Maximum value of items is " << sol.knapsack01(wt, val, n, W);

    return 0;
}

import java.util.*;

class Solution {
    // Function to solve the 0/1 Knapsack problem with arrays
    private int func(int[] wt, int[] val, int ind, int W, int[][] dp) {
        /* Base case: If there are no items left
        or the knapsack has no capacity, return 0 */
        if (ind < 0 || W == 0) {
            return 0;
        }

        /* If the result for this state is
        already calculated, return it */
        if (dp[ind][W] != -1) {
            return dp[ind][W];
        }

        /* Calculate the maximum value by either
        excluding the current item or including it */
        int notTaken = func(wt, val, ind - 1, W, dp);
        int taken = 0;

        /* Check if the current item can be included
        without exceeding the knapsack's capacity */
        if (wt[ind] <= W) {
            taken = val[ind] + func(wt, val, ind - 1, W - wt[ind], dp);
        }

        // Store the result in the DP table and return
        dp[ind][W] = Math.max(notTaken, taken);
        return dp[ind][W];
    }

    public int knapsack01(int[] wt, int[] val, int n, int W) { 
        // Initialize DP table with -1
        int[][] dp = new int[n][W + 1];
        for (int[] row : dp) {
            Arrays.fill(row, -1);
        }
        return func(wt, val, n - 1, W, dp);
    }

    public static void main(String[] args) {
        int[] wt = {1, 2, 4, 5};
        int[] val = {5, 4, 8, 6};
        int W = 5;
        int n = wt.length;
        
        // Create an instance of Solution class
        Solution sol = new Solution();

        System.out.println("The Maximum value of items is " + sol.knapsack01(wt, val, n, W));
    }
}
class Solution:
    # Function to solve the 0/1 Knapsack problem with arrays
    def func(self, wt, val, ind, W, dp):
        """ Base case: If there are no items left 
        or the knapsack has no capacity, return 0"""
        if ind < 0 or W == 0:
            return 0

        """ If the result for this state is
        already calculated, return it"""
        if dp[ind][W] != -1:
            return dp[ind][W]

        """ Calculate the maximum value by either
        excluding the current item or including it"""
        not_taken = self.func(wt, val, ind - 1, W, dp)
        taken = 0

        """ Check if the current item can be included
        without exceeding the knapsack's capacity"""
        if wt[ind] <= W:
            taken = val[ind] + self.func(wt, val, ind - 1, W - wt[ind], dp)

        # Store the result in the DP table and return
        dp[ind][W] = max(not_taken, taken)
        return dp[ind][W]

    def knapsack01(self, wt, val, n, W):
        # Initialize DP table with -1
        dp = [[-1 for _ in range(W + 1)] for _ in range(n)]
        return self.func(wt, val, n - 1, W, dp)

# Main execution
if __name__ == "__main__":
    wt = [1, 2, 4, 5]
    val = [5, 4, 8, 6]
    W = 5
    n = len(wt)

    # Create an instance of Solution class
    sol = Solution()

    print("The Maximum value of items is", sol.knapsack01(wt, val, n, W))
class Solution {
    // Function to solve the 0/1 Knapsack problem with arrays
    func(wt, val, ind, W, dp) {
        /* Base case: If there are no items left
        or the knapsack has no capacity, return 0*/
        if (ind < 0 || W === 0) {
            return 0;
        }

        /* If the result for this state is
        already calculated, return it*/
        if (dp[ind][W] !== -1) {
            return dp[ind][W];
        }

        /* Calculate the maximum value by either
        excluding the current item or including it*/
        const notTaken = this.func(wt, val, ind - 1, W, dp);
        let taken = 0;

        /* Check if the current item can be included
        without exceeding the knapsack's capacity*/
        if (wt[ind] <= W) {
            taken = val[ind] + this.func(wt, val, ind - 1, W - wt[ind], dp);
        }

        // Store the result in the DP table and return
        dp[ind][W] = Math.max(notTaken, taken);
        return dp[ind][W];
    }

    knapsack01(wt, val, n, W) {
        // Initialize DP table with -1
        const dp = Array.from({ length: n }, () => Array(W + 1).fill(-1));
        return this.func(wt, val, n - 1, W, dp);
    }
}

// Main execution
const wt = [1, 2, 4, 5];
const val = [5, 4, 8, 6];
const W = 5;
const n = wt.length;

// Create an instance of Solution class
const sol = new Solution();

console.log("The Maximum value of items is", sol.knapsack01(wt, val, n, W));

Complexity Analysis:

Time Complexity: O(N*W), where N is the size of the array and W is the capacity of the knapsack. There are N*W states therefore at max ‘N*W’ new problems will be solved.

Space Complexity:O(N*W) + O(N), We are using a recursion stack space(O(N)) and a 2D array ( O(N*W)).

In order to convert a recursive code to tabulation code, we try to convert the recursive code to tabulation and here are the steps:

Declare a dp array of size [n][W+1]: As there are two changing parameters in the recursive solution, 'ind' and 'target'. The size of the input array is ‘N’, so the index will always lie between ‘0’ and ‘n-1’. The capacity can take any value between ‘0’ and ‘W’. Therefore 2D dp array(dp[n][W+1]) is needed. Set its type as int and initialize it as 0.
Setting Base Cases in the Array: In the recursive code, our base condition was when ind == 0, it meant we were at the first item, so in that case were checking whether this item’s weight is less than or equal to the current capacity W, if it was, we were simply returning its value (val[0]) else we were returning 0. So, will set the same value for 'ind' = 0 in the dp array.

Iterative Computation Using Loops: Initialize two nested for loops to traverse the dp array. First loop will run from 1 to n-1 as we are done for the ind = 0 for the base case and the second loop will run from 0 to 'W'.
Now, following the same logic as discussed in the recursive approach, set the value of each cell in the 2D dp array. Instead of recursive calls, use the dp array itself to find the values of intermediate calculations.
Returning the answer: At last dp[n-1][W] will hold the solution after the completion of whole process, as we are doing the calculations in bottom-up manner.

#include <bits/stdc++.h>
using namespace std;

class Solution{
public:  
    // Function to solve the 0/1 Knapsack problem
    int knapsack01(vector<int>& wt, vector<int>& val, int n, int W) {
        /* Declare a 2D DP table with dimensions
        n x W+1 and initialize it with zeros*/
        vector<vector<int>> dp(n, vector<int>(W + 1, 0));

        /* Base condition: Fill in the first 
        row for the weight of the first item*/
        for (int i = wt[0]; i <= W; i++) {
            dp[0][i] = val[0];
        }

        // Fill in DP table using a bottom-up approach
        for (int ind = 1; ind < n; ind++) {
            for (int cap = 0; cap <= W; cap++) {
                /* Calculate the maximum value by either
                excluding the current item or including it*/
                int notTaken = dp[ind - 1][cap];
                int taken = INT_MIN;

                /* Check if the current item can be included
                without exceeding the knapsack's capacity*/
                if (wt[ind] <= cap) {
                    taken = val[ind] + dp[ind - 1][cap - wt[ind]];
                }

                // Update the DP table
                dp[ind][cap] = max(notTaken, taken);
            }
        }

        // The final result is in last cell
        return dp[n - 1][W];
    }
};

int main() {
    vector<int> wt = {1, 2, 4, 5};
    vector<int> val = {5, 4, 8, 6};
    int W = 5;
    int n = wt.size();

    
    //Create an instance of Solution class
    Solution sol;
    
    // Call the function to find the minimum coins
    int result = sol.knapsack01(wt, val, n, W);
    
    // Output the result
    cout << "The Maximum value of items is " << result << endl;
    
    return 0; 
}

import java.util.Arrays;

class Solution {
    // Function to solve the 0/1 Knapsack problem
    public int knapsack01(int[] wt, int[] val, int n, int W) {
        /* Declare a 2D DP table with dimensions
        n x W+1 and initialize it with zeros*/
        int[][] dp = new int[n][W + 1];

        /* Base condition: Fill in the first 
        row for the weight of the first item*/
        for (int i = wt[0]; i <= W; i++) {
            dp[0][i] = val[0];
        }

        // Fill in DP table using a bottom-up approach
        for (int ind = 1; ind < n; ind++) {
            for (int cap = 0; cap <= W; cap++) {
                /* Calculate the maximum value by either
                excluding the current item or including it*/
                int notTaken = dp[ind - 1][cap];
                int taken = Integer.MIN_VALUE;

                /* Check if the current item can be included
                without exceeding the knapsack's capacity*/
                if (wt[ind] <= cap) {
                    taken = val[ind] + dp[ind - 1][cap - wt[ind]];
                }

                // Update the DP table
                dp[ind][cap] = Math.max(notTaken, taken);
            }
        }

        // The final result is in the last cell
        return dp[n - 1][W];
    }

    public static void main(String[] args) {
        int[] wt = {1, 2, 4, 5};
        int[] val = {5, 4, 8, 6};
        int W = 5;
        int n = wt.length;

        // Create an instance of Solution class
        Solution sol = new Solution();
        
        // Call the function to find the maximum value
        int result = sol.knapsack01(wt, val, n, W);
        
        // Output the result
        System.out.println("The Maximum value of items is " + result);
    }
}
class Solution:
    # Function to solve 0/1 Knapsack problem
    def knapsack01(self, wt, val, n, W):
        """ Declare a 2D DP table with dimensions 
        n x W+1 and initialize it with zeros"""
        dp = [[0] * (W + 1) for _ in range(n)]

        """ Base condition: Fill in the first row 
        for the weight of the first item"""
        for i in range(wt[0], W + 1):
            dp[0][i] = val[0]

        # Fill in DP table using a bottom-up approach
        for ind in range(1, n):
            for cap in range(W + 1):
                """ Calculate the maximum value by either 
                excluding the current item or including it"""
                notTaken = dp[ind - 1][cap]
                taken = float('-inf')

                """ Check if the current item can be included 
                without exceeding the knapsack's capacity"""
                if wt[ind] <= cap:
                    taken = val[ind] + dp[ind - 1][cap - wt[ind]]

                # Update the DP table
                dp[ind][cap] = max(notTaken, taken)

        # The final result is in the last cell
        return dp[n - 1][W]

wt = [1, 2, 4, 5]
val = [5, 4, 8, 6]
W = 5
n = len(wt)

# Create an instance of Solution class
sol = Solution()

# Call the function to find the maximum value
result = sol.knapsack01(wt, val, n, W)

# Output the result
print("The Maximum value of items is", result)
class Solution {
    // Function to solve the 0/1 Knapsack problem
    knapsack01(wt, val, n, W) {
        /* Declare a 2D DP table with dimensions
        n x W+1 and initialize it with zeros*/
        let dp = Array.from({ length: n }, () => Array(W + 1).fill(0));

        /* Base condition: Fill in the first 
        row for the weight of the first item*/
        for (let i = wt[0]; i <= W; i++) {
            dp[0][i] = val[0];
        }

        // Fill in DP table using a bottom-up approach
        for (let ind = 1; ind < n; ind++) {
            for (let cap = 0; cap <= W; cap++) {
                /* Calculate the maximum value by either
                excluding the current item or including it*/
                let notTaken = dp[ind - 1][cap];
                let taken = Number.NEGATIVE_INFINITY;

                /* Check if the current item can be included
                without exceeding the knapsack's capacity*/
                if (wt[ind] <= cap) {
                    taken = val[ind] + dp[ind - 1][cap - wt[ind]];
                }

                // Update the DP table
                dp[ind][cap] = Math.max(notTaken, taken);
            }
        }

        // The final result is in the last cell
        return dp[n - 1][W];
    }
}

const wt = [1, 2, 4, 5];
const val = [5, 4, 8, 6];
const W = 5;
const n = wt.length;

// Create an instance of Solution class
const sol = new Solution();

// Call the function to find the maximum value
const result = sol.knapsack01(wt, val, n, W);

// Output the result
console.log("The Maximum value of items is " + result);

Complexity Analysis:

Time Complexity: O(N*W), where N is the size of the array. As two nested loops are used for the calculations.

Space Complexity:O(N*W), As a 2D array of size N*W is used.

If we observe the relation, dp[ind][cap] = max(dp[ind-1][cap] ,dp[ind-1][cap-wt[ind]]. We find that to calculate a value of a cell of the dp array, we need only the previous row values (say prev). So, we don’t need to store an entire array. Hence we can space optimize it. We will be space optimizing this solution using only one row.

Intuition:

If we closely observe, we fill in the following manner in two-row space optimization:

We will initialize the first row and then using its values we will the next row.

If we clearly see the values required: dp[ind-1][cap] and dp[ind-1][cap - wt[ind]], we can say that if we are at a column cap, we will only require the values shown in the green region and none in the red region shown in the below image ( because cap - wt[ind] will always be less than the cap).

As we don’t want values from the right, we can start filling this new row from the right rather than the left.

Now here is the catch, if we are filling from the right and at any time we need the previous row’s value of the leftward columns only, why do we need to have two rows in the first place? We can use a single row and overwrite the new computed values on itself in order to store it.

#include <bits/stdc++.h>
using namespace std;

class Solution{
public:  
    // Function to solve the 0/1 Knapsack problem
    int knapsack01(vector<int>& wt, vector<int>& val, int n, int W) {
        /* Initialize a vector 'prev' to represent 
        the previous row of the DP table*/
        vector<int> prev(W + 1, 0);

        /* Base condition: Fill in 'prev' 
        for the weight of the first item*/
        for (int i = wt[0]; i <= W; i++) {
            prev[i] = val[0];
        }

        // Fill in the table using a bottom-up approach
        for (int ind = 1; ind < n; ind++) {
            for (int cap = W; cap >= 0; cap--) {
                
                /* Calculate the maximum value by either
                excluding the current item or including it*/
                int notTaken = prev[cap];
                int taken = INT_MIN;

                /* Check if the current item can be included
                without exceeding the knapsack's capacity*/
                if (wt[ind] <= cap) {
                    taken = val[ind] + prev[cap - wt[ind]];
                }

                // Update 'prev' for the current capacity
                prev[cap] = max(notTaken, taken);
            }
        }

        /* The final result is in the 
        last cell of the 'prev' vector*/
        return prev[W];
    }
};

int main() {
    vector<int> wt = {1, 2, 4, 5};
    vector<int> val = {5, 4, 8, 6};
    int W = 5;
    int n = wt.size();

    
    //Create an instance of Solution class
    Solution sol;
    
    // Call the function to find the minimum coins
    int result = sol.knapsack01(wt, val, n, W);
    
    // Output the result
    cout << "The Maximum value of items is " << result << endl;
    
    return 0; 
}

import java.util.*;

class Solution {
    // Function to solve the 0/1 Knapsack problem
    public int knapsack01(int[] wt, int[] val, int n, int W) {
        /* Initialize a vector 'prev' to represent 
        the previous row of the DP table*/
        int[] prev = new int[W + 1];

        /* Base condition: Fill in 'prev' 
        for the weight of the first item*/
        for (int i = wt[0]; i <= W; i++) {
            prev[i] = val[0];
        }

        // Fill in the table using a bottom-up approach
        for (int ind = 1; ind < n; ind++) {
            for (int cap = W; cap >= 0; cap--) {
                /* Calculate the maximum value by either 
                excluding the current item or including it*/
                int notTaken = prev[cap];
                int taken = Integer.MIN_VALUE;

                /* Check if the current item can be included 
                without exceeding the knapsack's capacity*/
                if (wt[ind] <= cap) {
                    taken = val[ind] + prev[cap - wt[ind]];
                }

                // Update 'prev' for the current capacity
                prev[cap] = Math.max(notTaken, taken);
            }
        }

        /* The final result is in the
        last cell of the 'prev' vector*/
        return prev[W];
    }

    public static void main(String[] args) {
        int[] wt = {1, 2, 4, 5};
        int[] val = {5, 4, 8, 6};
        int W = 5;
        int n = wt.length;

        // Create an instance of Solution class
        Solution sol = new Solution();

        // Call the function to find the maximum value
        int result = sol.knapsack01(wt, val, n, W);

        // Output the result
        System.out.println("The Maximum value of items is " + result);
    }
}
class Solution:
    # Function to solve the 0/1 Knapsack problem
    def knapsack01(self, wt, val, n, W):
        """ Initialize a vector 'prev' to represent
        the previous row of the DP table"""
        prev = [0] * (W + 1)

        """ Base condition: Fill in 'prev' 
        for the weight of the first item"""
        for i in range(wt[0], W + 1):
            prev[i] = val[0]

        # Fill in the table using a bottom-up approach
        for ind in range(1, n):
            for cap in range(W, -1, -1):
                """ Calculate the maximum value by either 
                excluding the current item or including it"""
                notTaken = prev[cap]
                taken = float('-inf')

                """ Check if the current item can be included
                without exceeding the knapsack's capacity"""
                if wt[ind] <= cap:
                    taken = val[ind] + prev[cap - wt[ind]]

                # Update 'prev' for the current capacity
                prev[cap] = max(notTaken, taken)

        """ The final result is in the 
        last cell of the 'prev' vector"""
        return prev[W]

wt = [1, 2, 4, 5]
val = [5, 4, 8, 6]
W = 5
n = len(wt)

# Create an instance of Solution class
sol = Solution()

# Call the function to find the maximum value
result = sol.knapsack01(wt, val, n, W)

# Output the result
print("The Maximum value of items is", result)
class Solution {
    // Function to solve the 0/1 Knapsack problem
    knapsack01(wt, val, n, W) {
        /* Initialize a vector 'prev' to represent
        the previous row of the DP table*/
        let prev = Array(W + 1).fill(0);

        /* Base condition: Fill in 'prev' 
        for the weight of the first item*/
        for (let i = wt[0]; i <= W; i++) {
            prev[i] = val[0];
        }

        // Fill in the table using a bottom-up approach
        for (let ind = 1; ind < n; ind++) {
            for (let cap = W; cap >= 0; cap--) {
                /* Calculate the maximum value by either
                excluding the current item or including it*/
                let notTaken = prev[cap];
                let taken = Number.NEGATIVE_INFINITY;

                /* Check if the current item can be included
                without exceeding the knapsack's capacity*/
                if (wt[ind] <= cap) {
                    taken = val[ind] + prev[cap - wt[ind]];
                }

                // Update 'prev' for the current capacity
                prev[cap] = Math.max(notTaken, taken);
            }
        }

        /* The final result is in the 
        last cell of the 'prev' vector*/
        return prev[W];
    }
}

const wt = [1, 2, 4, 5];
const val = [5, 4, 8, 6];
const W = 5;
const n = wt.length;

// Create an instance of Solution class
const sol = new Solution();

// Call the function to find the maximum value
const result = sol.knapsack01(wt, val, n, W);

// Output the result
console.log("The Maximum value of items is " + result);

Complexity Analysis:

Time Complexity: O(N*W), where N is the size of the array. As two nested loops are used for the calculations.

Space Complexity:O(W), We are using an external array of size ‘W+1’ to store only one row.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Why a Greedy Solution will not work:

Steps to form the recursive solution:

Complexity Analysis:

Complexity Analysis:

Complexity Analysis:

Intuition:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code