Unbounded knapsack

Why a Greedy Solution will not work:

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.

As the greedy approach doesn’t work, we will try to generate all possible combinations using recursion and select the combination which gives us the maximum value in the given constraints.

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 upto which the array items are being considered. There is one more parameter “W”, to keep track of the capacity of the knapsack to decide whether we can pick an array item or not.

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 maximize the sum of the values of the selected items 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. So, use the pick/non-pick technique. There are two choices for every index:

Exclude the current element from the knapsack: First try to find a solution 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 call the recursive function f(ind-1,W).

Include the current element in the knapsack: Try to find a solution 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.

Now here is the catch, as there is an unlimited supply of coins, we want to again form a solution with the same item value. So we will not recursively call for f(ind-1, W-wt[ind]) rather stay at that index only and call for f(ind, W-wt[ind]) to find the answer.

Note: Consider the current item in the knapsack only when the current element’s weight is less than or equal to the capacity ‘W’ of the knapsack, if it isn’t do not consider it.

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

Return the maximum of 'take' and 'notTake': As we have to return the maximum amount of value, return the max 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 + f(ind, W-wt[ind])
    return max(notTake, take)
}

Base Cases: If ind==0, it means we are at the first item. Now, in an unbounded knapsack we can pick an item any number of times. As there is only one item left, pick for W/wt[0] times because ultimately we want to maximize the value of items while respecting the constraint of weight of the knapsack. The value added will be the product of the number of items picked and value of the individual item. Therefore return (W/wt[0]) * val[0].

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

class Solution{
private:
    // Function to solve the unbounded knapsack problem
    int func(vector<int>& wt, vector<int>& val, int ind, int W) {
        // Base case: if we're at the first item
        if (ind == 0) {
            /* Calculate and return the maximum 
            value for the given weight limit*/
            return (W / wt[0]) * val[0];
        }
        
        /* Calculate the maximum value
        without taking the current item*/
        int notTaken = 0 + func(wt, val, ind - 1, W);
    
        /* Calculate the maximum value
        by taking the current item*/
        int taken = INT_MIN;
        if (wt[ind] <= W)
            taken = val[ind] + func(wt, val, ind, W - wt[ind]);
        
        // Return the maximum value 
        return max(notTaken, taken);
    }
public:
    // Function to solve the unbounded knapsack problem
    int unboundedKnapsack(vector<int>& wt, vector<int>& val, int n, int W) {
    
        /* Call the utility function to 
        calculate the maximum value*/
        return func(wt, val, n - 1, W);
    }
};
int main() {
    vector<int> wt = {2, 4, 6}; 
    vector<int> val = {5, 11, 13};
    int W = 10;
    int n = wt.size(); 
    
    // Create an instance of Solution class
    Solution sol;
    
    cout << "The Maximum value of items the thief can steal is " << sol.unboundedKnapsack(wt, val, n, W) << endl;

    return 0; 
}

import java.util.*;

class Solution {
    // Function to solve the unbounded knapsack problem
    private int func(int[] wt, int[] val, int ind, int W) {
        // Base case: if we're at the first item
        if (ind == 0) {
            /* Calculate and return the maximum
            value for the given weight limit*/
            return (W / wt[0]) * val[0];
        }
        
        /* Calculate the maximum value 
        without taking the current item*/
        int notTaken = func(wt, val, ind - 1, W);
    
        /* Calculate the maximum value
        by taking the current item*/
        int taken = Integer.MIN_VALUE;
        if (wt[ind] <= W)
            taken = val[ind] + func(wt, val, ind, W - wt[ind]);
        
        // Return the maximum value 
        return Math.max(notTaken, taken);
    }
    
    // Function to solve the unbounded knapsack problem
    public int unboundedKnapsack(int[] wt, int[] val, int n, int W) {
    
        /* Call the utility function
        to calculate the maximum value*/
        return func(wt, val, n - 1, W);
    }

    public static void main(String[] args) {
        int[] wt = {2, 4, 6};
        int[] val = {5, 11, 13};
        int W = 10;
        int n = wt.length;
        
        // Create an instance of Solution class
        Solution sol = new Solution();
        
        System.out.println("The Maximum value of items the thief can steal is " + sol.unboundedKnapsack(wt, val, n, W));
    }
}
class Solution:
    #Function to solve the unbounded knapsack problem
    def func(self, wt, val, ind, W):
        # Base case: if we're at the first item
        if ind == 0:
            """ Calculate and return the maximum
            value for the given weight limit"""
            return (W // wt[0]) * val[0]
        
        """ Calculate the maximum value 
        without taking the current item"""
        not_taken = self.func(wt, val, ind - 1, W)
        
        """ Calculate the maximum value
        by taking the current item"""
        taken = float('-inf')
        if wt[ind] <= W:
            taken = val[ind] + self.func(wt, val, ind, W - wt[ind])
        
        """ Store the maximum value in
        the DP table and return it"""
        return max(not_taken, taken)
    
    # Function to solve the unbounded knapsack problem
    def unboundedKnapsack(self, wt, val, n, W):
        
        """ Call the utility function 
        to calculate the maximum value"""
        return self.func(wt, val, n - 1, W)

if __name__ == "__main__":
    wt = [2, 4, 6]
    val = [5, 11, 13]
    W = 10
    n = len(wt)
    
    # Create an instance of Solution class
    sol = Solution()
    
    print("The Maximum value of items the thief can steal is", sol.unboundedKnapsack(wt, val, n, W))
class Solution {
    // Function to solve the unbounded knapsack problem
    func(wt, val, ind, W) {
        // Base case: if we're at the first item
        if (ind === 0) {
            /* Calculate and return the maximum 
            value for the given weight limit*/
            return Math.floor(W / wt[0]) * val[0];
        }
        
        /* Calculate the maximum value 
        without taking the current item*/
        const notTaken = this.func(wt, val, ind - 1, W);
    
        /* Calculate the maximum value
        by taking the current item*/
        let taken = -Infinity;
        if (wt[ind] <= W) {
            taken = val[ind] + this.func(wt, val, ind, W - wt[ind]);
        }
        
        // Return the maximum value
        return Math.max(notTaken, taken);
    }
    
    // Function to solve the unbounded knapsack problem
    unboundedKnapsack(wt, val, n, W) {
        
        /* Call the utility function to
        calculate the maximum value*/
        return this.func(wt, val, n - 1, W);
    }
}

const wt = [2, 4, 6];
const val = [5, 11, 13];
const W = 10;
const n = wt.length;

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

console.log("The Maximum value of items the thief can steal is " + sol.unboundedKnapsack(wt, val, n, W));

Complexity Analysis:

Time Complexity:O(2^N), As each element has two choices and there are total N elements to be considered.
Space Complexity:O(N), As the maximum depth of the recursion stack can go upto 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 'W'. The maximum value 'ind' can attain is (n), where n is the size of array and for 'W', which denotes weight of the knapsack, only values between 0 to W. Therefore, we need 2D dp array.

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 unbounded knapsack problem
    int func(vector<int>& wt, vector<int>& val, int ind, int W, vector<vector<int>>& dp) {
        // Base case: if we're at the first item
        if (ind == 0) {
            /* Calculate and return the maximum 
            value for the given weight limit*/
            return (W / wt[0]) * val[0];
        }
    
        /* If the result for this index and weight
        limit is already calculated, return it*/
        if (dp[ind][W] != -1)
            return dp[ind][W];
        
        /* Calculate the maximum value
        without taking the current item*/
        int notTaken = 0 + func(wt, val, ind - 1, W, dp);
    
        /* Calculate the maximum value
        by taking the current item*/
        int taken = INT_MIN;
        if (wt[ind] <= W)
            taken = val[ind] + func(wt, val, ind, W - wt[ind], dp);
        
        /* Store the maximum value in
        the DP table and return it*/
        return dp[ind][W] = max(notTaken, taken);
    }
public:
    // Function to solve the unbounded knapsack problem
    int unboundedKnapsack(vector<int>& wt, vector<int>& val, int n, int W) {
        vector<vector<int>> dp(n, vector<int>(W + 1, -1)); 
    
        /* Call the utility function to 
        calculate the maximum value*/
        return func(wt, val, n - 1, W, dp);
    }
};
int main() {
    vector<int> wt = {2, 4, 6}; 
    vector<int> val = {5, 11, 13};
    int W = 10;
    int n = wt.size(); 
    
    // Create an instance of Solution class
    Solution sol;
    
    cout << "The Maximum value of items the thief can steal is " << sol.unboundedKnapsack(wt, val, n, W) << endl;

    return 0; 
}

import java.util.*;

class Solution {
    // Function to solve the unbounded knapsack problem
    private int func(int[] wt, int[] val, int ind, int W, int[][] dp) {
        // Base case: if we're at the first item
        if (ind == 0) {
            /* Calculate and return the maximum
            value for the given weight limit*/
            return (W / wt[0]) * val[0];
        }
    
        /* If the result for this index and weight
        limit is already calculated, return it*/
        if (dp[ind][W] != -1)
            return dp[ind][W];
        
        /* Calculate the maximum value 
        without taking the current item*/
        int notTaken = func(wt, val, ind - 1, W, dp);
    
        /* Calculate the maximum value
        by taking the current item*/
        int taken = Integer.MIN_VALUE;
        if (wt[ind] <= W)
            taken = val[ind] + func(wt, val, ind, W - wt[ind], dp);
        
        /* Store the maximum value in
        the DP table and return it*/
        return dp[ind][W] = Math.max(notTaken, taken);
    }
    
    // Function to solve the unbounded knapsack problem
    public int unboundedKnapsack(int[] wt, int[] val, int n, int W) {
        int[][] dp = new int[n][W + 1];
        for (int[] row : dp) {
            Arrays.fill(row, -1);
        }
    
        /* Call the utility function
        to calculate the maximum value*/
        return func(wt, val, n - 1, W, dp);
    }

    public static void main(String[] args) {
        int[] wt = {2, 4, 6};
        int[] val = {5, 11, 13};
        int W = 10;
        int n = wt.length;
        
        // Create an instance of Solution class
        Solution sol = new Solution();
        
        System.out.println("The Maximum value of items the thief can steal is " + sol.unboundedKnapsack(wt, val, n, W));
    }
}
class Solution:
    #Function to solve the unbounded knapsack problem
    def func(self, wt, val, ind, W, dp):
        # Base case: if we're at the first item
        if ind == 0:
            """ Calculate and return the maximum
            value for the given weight limit"""
            return (W // wt[0]) * val[0]
        
        """ If the result for this index and weight
        limit is already calculated, return it"""
        if dp[ind][W] != -1:
            return dp[ind][W]
        
        """ Calculate the maximum value 
        without taking the current item"""
        not_taken = self.func(wt, val, ind - 1, W, dp)
        
        """ Calculate the maximum value
        by taking the current item"""
        taken = float('-inf')
        if wt[ind] <= W:
            taken = val[ind] + self.func(wt, val, ind, W - wt[ind], dp)
        
        """ Store the maximum value in
        the DP table and return it"""
        dp[ind][W] = max(not_taken, taken)
        return dp[ind][W]
    
    # Function to solve the unbounded knapsack problem
    def unboundedKnapsack(self, wt, val, n, W):
        dp = [[-1] * (W + 1) for _ in range(n)]
        
        """ Call the utility function 
        to calculate the maximum value"""
        return self.func(wt, val, n - 1, W, dp)

if __name__ == "__main__":
    wt = [2, 4, 6]
    val = [5, 11, 13]
    W = 10
    n = len(wt)
    
    # Create an instance of Solution class
    sol = Solution()
    
    print("The Maximum value of items the thief can steal is", sol.unboundedKnapsack(wt, val, n, W))
class Solution {
    // Function to solve the unbounded knapsack problem
    func(wt, val, ind, W, dp) {
        // Base case: if we're at the first item
        if (ind === 0) {
            /* Calculate and return the maximum 
            value for the given weight limit*/
            return Math.floor(W / wt[0]) * val[0];
        }
    
        /* If the result for this index and weight
        limit is already calculated, return it*/
        if (dp[ind][W] !== -1) {
            return dp[ind][W];
        }
        
        /* Calculate the maximum value 
        without taking the current item*/
        const notTaken = this.func(wt, val, ind - 1, W, dp);
    
        /* Calculate the maximum value
        by taking the current item*/
        let taken = -Infinity;
        if (wt[ind] <= W) {
            taken = val[ind] + this.func(wt, val, ind, W - wt[ind], dp);
        }
        
        /* Store the maximum value in
        the DP table and return it*/
        dp[ind][W] = Math.max(notTaken, taken);
        return dp[ind][W];
    }
    
    // Function to solve the unbounded knapsack problem
    unboundedKnapsack(wt, val, n, W) {
        const dp = Array.from({ length: n }, () => Array(W + 1).fill(-1));
        
        /* Call the utility function to
        calculate the maximum value*/
        return this.func(wt, val, n - 1, W, dp);
    }
}

const wt = [2, 4, 6];
const val = [5, 11, 13];
const W = 10;
const n = wt.length;

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

console.log("The Maximum value of items the thief can steal is " + sol.unboundedKnapsack(wt, val, n, W));

Complexity Analysis:

Time Complexity:O(N*W), as there are N*W states therefore at max ‘N*W’ new problems will be solved.

Space Complexity:O(N*W) + O(N), the stack space will be O(N) and a 2D array of size N*W is used.

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 'W'. The maximum value 'ind' can attain is (n) and including 0 its n, where n is the size of array, for 'W' can have any values between 0 to 'W'. So we need a 2D dp array. 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 means we were considering the first element. So for 'ind' == 0, assign (i/wt[0]) * val[0] to the dp array, where i will iterate from 0 to W.
Iterative Computation Using Loops: As we are done for the first row(ind = 0) in the base case, so ‘ind’ variable will move from 1 to n-1, whereas ‘W’ variable will move from 0 to 'W'(weight). Initialize two nested for loops to traverse the dp array and following the logic 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 unbounded knapsack problem
    int unboundedKnapsack(vector<int>& wt, vector<int>& val, int n, int W) {
        vector<vector<int>> dp(n, vector<int>(W + 1, 0)); 

        // Base Condition
        for (int i = wt[0]; i <= W; i++) {
            // Calculate maximum value for the first item
            dp[0][i] = (i / wt[0]) * val[0];
        }

        for (int ind = 1; ind < n; ind++) {
            for (int cap = 0; cap <= W; cap++) {
                // Maximum value without taking current item
                int notTaken = 0 + dp[ind - 1][cap]; 

                int taken = INT_MIN;
                if (wt[ind] <= cap)
                    // Maximum value by taking current item
                    taken = val[ind] + dp[ind][cap - wt[ind]]; 
                
                // Store the maximum value in the DP table
                dp[ind][cap] = max(notTaken, taken); 
            }
        }
        /* Return the maximum value considering
        all items and the knapsack capacity*/
        return dp[n - 1][W]; 
    }
};

int main() {
    vector<int> wt = {2, 4, 6}; 
    vector<int> val = {5, 11, 13}; 
    int W = 10; 
    int n = wt.size(); 
    
    //Create an instance of Solution class
    Solution sol;

    // Print the result
    cout << "The Maximum value of items the thief can steal is " << sol.unboundedKnapsack(wt, val, n, W) << endl;

    return 0; 
}

import java.util.*;

class Solution {
    // Function to solve the unbounded knapsack problem
    public int unboundedKnapsack(int[] wt, int[] val, int n, int W) {
        int[][] dp = new int[n][W + 1];

        // Base Condition
        for (int i = wt[0]; i <= W; i++) {
            // Calculate maximum value for the first item
            dp[0][i] = (i / wt[0]) * val[0];
        }

        for (int ind = 1; ind < n; ind++) {
            for (int cap = 0; cap <= W; cap++) {
                // Maximum value without taking current item
                int notTaken = dp[ind - 1][cap];

                int taken = Integer.MIN_VALUE;
                if (wt[ind] <= cap)
                    // Maximum value by taking current item
                    taken = val[ind] + dp[ind][cap - wt[ind]];

                // Store the maximum value in the DP table
                dp[ind][cap] = Math.max(notTaken, taken);
            }
        }
        /* Return the maximum value considering 
        all items and the knapsack capacity*/
        return dp[n - 1][W];
    }

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

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

        // Print the result
        System.out.println("The Maximum value of items the thief can steal is " + sol.unboundedKnapsack(wt, val, n, W));
    }
}
class Solution:
    # Function to solve the unbounded knapsack problem
    def unboundedKnapsack(self, wt, val, n, W):
        dp = [[0] * (W + 1) for _ in range(n)]

        # Base Condition
        for i in range(wt[0], W + 1):
            # Calculate maximum value for the first item
            dp[0][i] = (i // wt[0]) * val[0]

        for ind in range(1, n):
            for cap in range(W + 1):
                # Maximum value without taking current item
                not_taken = dp[ind - 1][cap]

                taken = float('-inf')
                if wt[ind] <= cap:
                    # Maximum value by taking current item
                    taken = val[ind] + dp[ind][cap - wt[ind]]

                # Store the maximum value in the DP table
                dp[ind][cap] = max(not_taken, taken)
        
        """ Return the maximum value considering
        all items and the knapsack capacity"""
        return dp[n - 1][W]

if __name__ == "__main__":
    wt = [2, 4, 6]
    val = [5, 11, 13]
    W = 10
    n = len(wt)

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

    # Print the result
    print("The Maximum value of items the thief can steal is", sol.unboundedKnapsack(wt, val, n, W))
class Solution {
    // Function to solve the unbounded knapsack problem
    unboundedKnapsack(wt, val, n, W) {
        const dp = Array.from({ length: n }, () => Array(W + 1).fill(0));

        // Base Condition
        for (let i = wt[0]; i <= W; i++) {
            // Calculate maximum value for the first item
            dp[0][i] = Math.floor(i / wt[0]) * val[0];
        }

        for (let ind = 1; ind < n; ind++) {
            for (let cap = 0; cap <= W; cap++) {
                // Maximum value without taking current item
                const notTaken = dp[ind - 1][cap];

                let taken = -Infinity;
                if (wt[ind] <= cap) {
                    // Maximum value by taking current item
                    taken = val[ind] + dp[ind][cap - wt[ind]];
                }

                // Store the maximum value in the DP table
                dp[ind][cap] = Math.max(notTaken, taken);
            }
        }
        /* Return the maximum value considering 
        all items and the knapsack capacity*/
        return dp[n - 1][W];
    }
}

const wt = [2, 4, 6];
const val = [5, 11, 13];
const W = 10;
const n = wt.length;

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

// Print the result
console.log("The Maximum value of items the thief can steal is " + sol.unboundedKnapsack(wt, val, n, W));

Complexity Analysis:

Time Complexity:O(N*W), There are two nested loops which accounts for N*W.

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

If we observe the relation obtained in the tabulation approach, dp[ind][cap] = max(dp[ind-1][cap] ,dp[ind][cap-wt[ind]]. We find that to calculate a value of a cell of the dp array, only the previous row values (say prev) are needed. 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.

Understanding:

In the relation, dp[ind-1][cap] and dp[ind-1][cap - wt[ind]], if we are at a column, only the same column value from previous row is required and other values will be from the current row itself. So we do not need to store an entire array for it.

We can use the 'cur' row itself to store the required value in the following way:

Somehow make sure that the previous value( say preValue) is available to us in some manner ( we will discuss later how we got the value).
Now, let us say that we want to find the value of cell cur[3], by going through the relation we find that we need a 'preValue' and one value from the 'cur' row.
To calculate the cur[3] element, we need only a single variable (preValue). The catch is that we can initially place this preValue at the position cur[3] (before finding its updated value) and later while calculating for the current row’s cell cur[3], the value present there automatically serves as the preValue and we can use it to find the required cur[3] value.
After calculating the cur[3] value we store it at the cur[3] position so this cur[3] will automatically serve as preValue for the next row. In this way, we space-optimize the tabulation approach by just using one row.

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

class Solution{
public:
    // Function to solve the unbounded knapsack problem
    int unboundedKnapsack(vector<int>& wt, vector<int>& val, int n, int W) {
        // Create a vector to store current DP state
        vector<int> cur(W + 1, 0); 

        // Base Condition
        for (int i = wt[0]; i <= W; i++) {
            // Calculate the maximum value for first item
            cur[i] = (i / wt[0]) * val[0]; 
        }

        for (int ind = 1; ind < n; ind++) {
            for (int cap = 0; cap <= W; cap++) {
                // Maximum value without taking current item
                int notTaken = cur[cap];  

                int taken = INT_MIN;
                if (wt[ind] <= cap)
                    // Maximum value by taking current item
                    taken = val[ind] + cur[cap - wt[ind]]; 

                /* Store the maximum value 
                in the current DP state*/
                cur[cap] = max(notTaken, taken); 
            }
        }
        /* Return the maximum value considering
        all items and the knapsack capacity*/
        return cur[W]; 
    }
};

int main() {
    vector<int> wt = {2, 4, 6}; 
    vector<int> val = {5, 11, 13}; 
    int W = 10; 
    int n = wt.size(); 
    
    //Create an instance of Solution class
    Solution sol;

    // Print the result
    cout << "The Maximum value of items the thief can steal is " << sol.unboundedKnapsack(wt, val, n, W) << endl;

    return 0; 
}

import java.util.*;

class Solution {
    // Function to solve the unbounded knapsack problem
    public int unboundedKnapsack(int[] wt, int[] val, int n, int W) {
        // Create a vector to store current DP state
        int[] cur = new int[W + 1];

        // Base Condition
        for (int i = wt[0]; i <= W; i++) {
            // Calculate the maximum value for first item
            cur[i] = (i / wt[0]) * val[0];
        }

        for (int ind = 1; ind < n; ind++) {
            for (int cap = 0; cap <= W; cap++) {
                // Maximum value without taking current item
                int notTaken = cur[cap];

                int taken = Integer.MIN_VALUE;
                if (wt[ind] <= cap)
                    // Maximum value by taking current item
                    taken = val[ind] + cur[cap - wt[ind]];

                /* Store the maximum value 
                in the current DP state*/
                cur[cap] = Math.max(notTaken, taken);
            }
        }
        /* Return the maximum value considering
        all items and the knapsack capacity*/
        return cur[W];
    }
}

public class Main {
    public static void main(String[] args) {
        int[] wt = {2, 4, 6};
        int[] val = {5, 11, 13};
        int W = 10;
        int n = wt.length;

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

        // Print the result
        System.out.println("The Maximum value of items the thief can steal is " + sol.unboundedKnapsack(wt, val, n, W));
    }
}
class Solution:
    # Function to solve the unbounded knapsack problem
    def unboundedKnapsack(self, wt, val, n, W):
        # Create a list to store current DP state
        cur = [0] * (W + 1)

        # Base Condition
        for i in range(wt[0], W + 1):
            # Calculate the maximum value for first item
            cur[i] = (i // wt[0]) * val[0]

        for ind in range(1, n):
            for cap in range(W + 1):
                # Maximum value without taking current item
                notTaken = cur[cap]

                taken = float('-inf')
                if wt[ind] <= cap:
                    # Maximum value by taking current item
                    taken = val[ind] + cur[cap - wt[ind]]

                # Store the maximum value in the current DP state
                cur[cap] = max(notTaken, taken)

        """ Return the maximum value considering 
        all items and the knapsack capacity"""
        return cur[W]

if __name__ == "__main__":
    wt = [2, 4, 6]
    val = [5, 11, 13]
    W = 10
    n = len(wt)

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

    # Print the result
    print("The Maximum value of items the thief can steal is", sol.unboundedKnapsack(wt, val, n, W))
class Solution {
    // Function to solve the unbounded knapsack problem
    unboundedKnapsack(wt, val, n, W) {
        // Create an array to store current DP state
        let cur = new Array(W + 1).fill(0);

        // Base Condition
        for (let i = wt[0]; i <= W; i++) {
            // Calculate the maximum value for first item
            cur[i] = Math.floor(i / wt[0]) * val[0];
        }

        for (let ind = 1; ind < n; ind++) {
            for (let cap = 0; cap <= W; cap++) {
                // Maximum value without taking current item
                let notTaken = cur[cap];

                let taken = Number.MIN_SAFE_INTEGER;
                if (wt[ind] <= cap) {
                    // Maximum value by taking current item
                    taken = val[ind] + cur[cap - wt[ind]];
                }

                // Store the maximum value in the current DP state
                cur[cap] = Math.max(notTaken, taken);
            }
        }
        /* Return the maximum value considering
        all items and the knapsack capacity*/
        return cur[W];
    }
}

const wt = [2, 4, 6];
const val = [5, 11, 13];
const W = 10;
const n = wt.length;

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

// Print the result
console.log("The Maximum value of items the thief can steal is " + sol.unboundedKnapsack(wt, val, n, W));

Complexity Analysis:

Time Complexity:O(N*W), There are two nested loops which accounts for N*W.

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:

Understanding:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code