The knapsack problem is a classic optimization problem in computer science where given a set of items, each with a weight and a value, and a knapsack with a maximum weight capacity, the goal is to maximize the total value of items that can be included in the knapsack without exceeding its capacity.

Variations of Knapsack Problem

1. 0/1 Knapsack Problem:
   1. In this variation, items can either be included or excluded from the knapsack. You cannot take fractions of items.
   2. Objective: Maximize the total value of items without exceeding the knapsack's weight capacity.
2. Fractional Knapsack Problem:
   1. In this variation, items can be included in fractions. You can take fractions of items according to their weight.
   2. Objective: Maximize the total value of items without exceeding the knapsack's weight capacity.
3. Unbounded Knapsack Problem:
   1. In this variation, there is an unlimited supply of each item. You can take as many instances of each item as you want.
   2. Objective: Maximize the total value of items without exceeding the knapsack's weight capacity.
4. Multiple Knapsack Problem:
   1. In this variation, there are multiple knapsacks, each with it own capacity. You need to distribute the items among the knapsacks to maximize the total value.
   2. Objective: Maximize the total value of items while respecting the capacity constraints of each knapsack.
5. Bounded Knapsack Problem:
   1. In this variation, there is a limited number of instances for each item. You cannot take more instances of an item than its given limit.
   2. Objective: Maximize the total value of items without exceeding the knapsack's weight capacity and respecting the limits on the number of instances for each item.

🅰️ 0 and 1 Knapsack

Problem Statement

Given two integer arrays, val and wt, each of size N, which represent the values and weights of N items respectively, and an integer W representing the maximum capacity of a knapsack, determine the maximum value achievable by selecting a subset of the items such that the total weight of the selected items does not exceed the knapsack capacity W.

Each item can either be picked in its entirety or not picked at all (0-1 property). The goal is to maximize the sum of the values of the selected items while keeping the total weight within the knapsack's capacity.

Example:

Example 1:

Input:
N = 4
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50

Output: 220

Explanation:
We have 3 items:
    Item 1: Value = 60, Weight = 10
    Item 2: Value = 100, Weight = 20
    Item 3: Value = 120, Weight = 30
The knapsack capacity W = 50

Optimal Selection:
    Pick Item 2 (Value = 100, Weight = 20)
    Pick Item 3 (Value = 120, Weight = 30)
Total Weight: 20 + 30 = 50
Maximum Value = 100 + 120 = 220

Example 2:

Input:
N = 3
val = [10, 20, 30]
wt = [1, 2, 3]
W = 5

Output: 50

Explanation:
We have 3 items:
    Item 1: Value = 10, Weight = 1
    Item 2: Value = 20, Weight = 2
    Item 3: Value = 30, Weight = 3
The knapsack capacity W  = 5

Optimal Solution:
    Pick Item 2 (Value = 20, Weight = 2)
    Pick Item 3 (Value = 30, Weight = 3)

Total Weight = 2 + 3 = 5
Maximum Value = 20 + 30 = 50

Different Approaches

1️⃣ Recursive Approach

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.

Code:

Start from the beginning (i = 0 to n)

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

class Solution {
    public:
    /* Recursive function to solve 0-1 Knapsack problem.
       Parameters:
       - `wt`: Array of weights of the items.
       - `val`: Array of values of the items.
       - `n`: Total number of items.
       - `index`: Current index in the items list.
       - `remainingCapacity`: Remaining capacity of the knapsack.
       Returns:
       - The maximum value achievable with the given constraints.
    */
    int knapsackRecursive(vector<int>& wt, vector<int>& val, int n, int index, int remainingCapacity) {
        // Base case: If we have considered all items or if the remaining capacity is 0.
        if (index >= n || remainingCapacity == 0) {
            return 0;
        }

        // Option 1: Exclude the current item (move to the next item).
        int excludeItem = knapsackRecursive(wt, val, n, index + 1, remainingCapacity);

        // Option 2: Include the current item (if the weight of the item is less than or equal to the remaining capacity).
        int includeItem = INT_MIN;
        if (wt[index] <= remainingCapacity) {
            includeItem = val[index] + knapsackRecursive(wt, val, n, index + 1, remainingCapacity - wt[index]);
        }

        // Return the maximum of including or excluding the current item.
        return max(includeItem, excludeItem);
    }

    /* Function to solve the 0-1 Knapsack problem using the recursive approach.
       Parameters:
       - `wt`: Array of weights of the items.
       - `val`: Array of values of the items.
       - `n`: Total number of items.
       - `W`: The maximum capacity of the knapsack.
       Returns:
       - The maximum value that can be obtained by selecting items without exceeding the knapsack capacity.
    */
    int knapsack01(vector<int>& wt, vector<int>& val, int n, int W) {
        return knapsackRecursive(wt, val, n, 0, W);
    }
};

int main() {
    // Example usage
    Solution sol;
    vector<int> weights = {2, 3, 4, 5}; // Weights of items
    vector<int> values = {3, 4, 5, 6};  // Corresponding values of items
    int n = weights.size(); // Total number of items
    int capacity = 5; // Maximum weight capacity of the knapsack

    // Call the knapsack function and print the result
    cout << "Maximum value in Knapsack: " << sol.knapsack01(weights, values, n, capacity) << endl;

    return 0;
}

Start from the end i.e., starting at the last index and moving towards 0.

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

class Solution {
public:
    // Recursive function starting from the last index
    int knapsack(int index, int W, vector<int>& wt, vector<int>& val) {
        // Base Case: when index is 0 (only first item left)
        if (index == 0) {
            if (wt[0] <= W) return val[0];
            else return 0;
        }

        // Choice 1: Don't pick the current item
        int notTake = knapsack(index - 1, W, wt, val);

        // Choice 2: Pick the current item (if it fits)
        int take = 0;
        if (wt[index] <= W) {
            take = val[index] + knapsack(index - 1, W - wt[index], wt, val);
        }

        // Return the maximum of picking or not picking
        return max(take, notTake);
    }
};

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

    Solution sol;
    cout << "Maximum value: " << sol.knapsack(n - 1, W, wt, val) << endl;

    return 0;
}

Complexity Analysis:

• Time Complexity: O(2 ^ n), where n is the size of the array.
• Space Complexity: O(n)

2️⃣ Memoization

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 encountered 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.

Code:

Starting from the Beginning (index = 0)

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

class Solution {
    public:
    /* 
    This function uses recursion with memoization (top-down approach) to solve the 0-1 Knapsack problem.
    Parameters:
    - `wt`: Array of weights of the items.
    - `val`: Array of values of the items.
    - `n`: Total number of items.
    - `index`: Current index in the item list being considered.
    - `remainingCapacity`: Remaining capacity of the knapsack.
    - `dp`: Memoization table to store the results of subproblems.

    Returns:
    - The maximum value achievable with the given constraints.
    */
    int knapsackRecursive(vector<int>& wt, vector<int>& val, int n, int index, int remainingCapacity, vector<vector<int>>& dp) {
        // Base case: if we have considered all items (index >= n).
        // No items left
        if (index >= n) {
            return 0;
        }

        // If this subproblem has already been solved, return the stored result.
        if (dp[index][remainingCapacity] != -1) {
            return dp[index][remainingCapacity];
        }

        // Option 1: Exclude the current item and move to the next item.
        int excludeItem = knapsackRecursive(wt, val, n, index + 1, remainingCapacity, dp);

        // Option 2: Include the current item (if its weight is less than or equal to the remaining capacity).
        int includeItem = INT_MIN; // Initialize to a very small value.
        if (wt[index] <= remainingCapacity) {
            // If we can include this item, reduce the remaining capacity and add the item's value.
            includeItem = val[index] + knapsackRecursive(wt, val, n, index + 1, remainingCapacity - wt[index], dp);
        }

        // Store the maximum value of either including or excluding the current item.
        return dp[index][remainingCapacity] = max(includeItem, excludeItem);
    }

   /* 
   This function initializes the memoization table and calls the recursive function.
   Parameters:
   - `wt`: Array of weights of the items.
   - `val`: Array of values of the items.
   - `n`: Total number of items.
   - `W`: Maximum weight capacity of the knapsack.

   Returns:
   - The maximum value that can be obtained by selecting items without exceeding the knapsack's weight capacity.
   */
   int knapsack01(vector<int>& wt, vector<int>& val, int n, int W) {
        // Initialize a 2D memoization table with -1, indicating that no subproblem has been solved yet.
        vector<vector<int>> dp(n, vector<int>(W + 1, -1));

        // Start the recursive process from the first item (index 0) and the full knapsack capacity W.
        return knapsackRecursive(wt, val, n, 0, W, dp);
    }
};

int main() {
    // Example usage of the knapsack problem.
    Solution sol;
    
    // Example weights and values of items.
    vector<int> weights = {2, 3, 4, 5};  // Weights of the items
    vector<int> values = {3, 4, 5, 6};   // Corresponding values of the items
    
    // Total number of items
    int n = weights.size();
    
    // Knapsack's maximum weight capacity
    int capacity = 5;

    // Call the knapsack01 function and print the maximum value achievable.
    cout << "Maximum value in Knapsack: " << sol.knapsack01(weights, values, n, capacity) << endl;

    return 0;
}

Starting from the End (index = n - 1)

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

class Solution {
public:
    int knapsack(int index, int W, vector<int>& wt, vector<int>& val, vector<vector<int>>& dp) {
        // Base Case: Only the first item is left
        if (index == 0) {
            if (wt[0] <= W) return val[0];
            else return 0;
        }

        // Memoization check
        if (dp[index][W] != -1) return dp[index][W];

        // Don't take the current item
        int notTake = knapsack(index - 1, W, wt, val, dp);

        // Take the current item (only if it fits)
        int take = 0;
        if (wt[index] <= W) {
            take = val[index] + knapsack(index - 1, W - wt[index], wt, val, dp);
        }

        // Save and return the best answer
        return dp[index][W] = max(take, notTake);
    }

    int knapsack01(vector<int>& wt, vector<int>& val, int W) {
        int n = wt.size();
        vector<vector<int>> dp(n, vector<int>(W + 1, -1));
        return knapsack(n - 1, W, wt, val, dp);
    }
};

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

    Solution sol;
    cout << "Maximum value: " << sol.knapsack01(wt, val, W) << endl;

    return 0;
}

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 2D array of size (n * W) and recursion stack space of n.

3️⃣ Tabulation (Bottom Up Approach)

Let's illustrate the problem with a simple example:

Suppose you have a knapsack with a weight capacity of 10 units and the following items:

The goal is to select items to maximize the total value while ensuring that the total weight does not exceed 10.

In order to convert a recursive code to tabulation we do the following 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.

Code:

#include <iostream>
#include <vector>

using namespace std;

int knapsack(int W, vector<int>& wt, vector<int>& val, int n) {
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= n; ++i) {
        for (int w = 1; w <= W; ++w) {
            if (wt[i - 1] <= w) {
                dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][W];
}

int main() {
    vector<int> wt = {2, 3, 5, 7};
    vector<int> val = {6, 5, 10, 12};
    int W = 10;
    int n = wt.size();

    cout << "Maximum value that can be obtained: " << knapsack(W, wt, val, n) << endl;

    return 0;
}

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

// Class to solve 0/1 Knapsack Problem
class Solution {
public:  
    // Function to solve the 0/1 Knapsack problem
    int knapsack01(vector<int>& weights, vector<int>& values, int n, int maxCapacity) {

        // Step 1: Declare a 2D DP table (n rows for items, maxCapacity+1 columns for capacities)
        vector<vector<int>> dp(n, vector<int>(maxCapacity + 1, 0));

        // Step 2: Initialize first row (only first item is available)
        // If weight of item 0 is <= current capacity, set value
        for (int capacity = weights[0]; capacity <= maxCapacity; capacity++) {
            dp[0][capacity] = values[0];
        }

        // Step 3: Fill the DP table using bottom-up approach
        for (int item = 1; item < n; item++) {          // For each item
            for (int capacity = 0; capacity <= maxCapacity; capacity++) {  // For each capacity
                
                // Step 4: Option 1 - Do not take the current item
                int notTake = dp[item - 1][capacity];

                // Step 5: Option 2 - Take the current item (if it fits)
                int take = INT_MIN;
                if (weights[item] <= capacity) {
                    take = values[item] + dp[item - 1][capacity - weights[item]];
                }

                // Step 6: Choose the better option (maximum value)
                dp[item][capacity] = max(notTake, take);
            }
        }

        // Step 7: The answer (maximum value) is stored at dp[n-1][maxCapacity]
        return dp[n - 1][maxCapacity];
    }
};

int main() {
    // Step 0: Input arrays for weights and values
    vector<int> weights = {1, 2, 4, 5};
    vector<int> values = {5, 4, 8, 6};
    int maxCapacity = 5;
    int numberOfItems = weights.size();

    // Step 1: Create an instance of Solution class
    Solution sol;

    // Step 2: Call the knapsack function to find the maximum value
    int maxValue = sol.knapsack01(weights, values, numberOfItems, maxCapacity);

    // Step 3: Output the result
    cout << "The Maximum value of items is " << maxValue << endl;
    
    return 0; 
}

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.

4️⃣ Space Optimized Approach

If we observe the relation:

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 using its value we will populate the new row.

In the normal tabulation (2D dp[i][j]):

• dp[i][j] = max value by considering items from 0 to i - 1 with capacity j.
• To compute dp[i][j], you only use values from previous row (i - 1):
  • dp[i - 1][j] (exclude the current item
  • dp[i - 1][j - wt[i] (include the current item)
• This tells us:
  • Only the previous row (i - 1) is needed to compute the current row (i).
  • We do not need the full dp table for all items.

So we can optimize like this:

• Store only two rows at a time:
  • prev → Represents dp[i - 1][…]
  • curr → Represents dp[i][…]
• After filling curr, copy it into prev for the next item.

Code:

class Solution {
public:
    int knapsack01(vector<int>& wt, vector<int>& val, int n, int W) {
        // Instead of a 2D dp array, we use two 1D arrays to save space
        vector<int> prev(W + 1, 0), curr(W + 1, 0);

        // Iterate over each item one by one
        for (int index = 1; index <= n; index++) {
            // For each possible weight capacity from 1 to W
            for (int currWt = 1; currWt <= W; currWt++) {
                
                // Step 1: Exclude the current item
                int exclude = prev[currWt];

                // Step 2: Include the current item (only if its weight <= current capacity)
                int include = INT_MIN;
                if (wt[index - 1] <= currWt) {
                    include = val[index - 1] + prev[currWt - wt[index - 1]];
                }

                // Step 3: Choose the maximum value between including and excluding the current item
                curr[currWt] = max(include, exclude);
            }

            // Step 4: After processing the current item, update 'prev' for the next iteration
            prev = curr;
        }

        // Step 5: The final answer is the maximum value we can achieve with full capacity W
        return prev[W];
    }
};

Complexity Analysis:

• Time Complexity:O(n*W)
• Space Complexity:O(2*W)
  • Overall: O(W)

🔥 Even more optimization:

🅱️ Unbounded Knapsack

Problem Statement

Given two integer arrays, val and wt, each of size N, representing the values and weights of N items respectively, and an integer W, representing the maximum capacity of a knapsack, determine the maximum value achievable by selecting a subset of the items such that the total weight of the selected items does not exceed the knapsack capacity W. The goal is to maximize the sum of the values of the selected items while keeping the total weight within the knapsack's capacity.

An infinite supply of each item can be assumed.

Examples

Example 1:

Input: val = [5, 11, 13], wt = [2, 4, 6], W = 10
Output: 27

Explanation: Select 2 items with weights 4 and 1 item with weight 2 for a total value of 11+11+5 = 27.

Example 2:

Input: val = [10, 40, 50, 70], wt = [1, 3, 4, 5], W = 8
Output: 110

Explanation: Select items with weights 3 and 5 for a total value of 40 + 70 = 110.

Different Approaches

1️⃣ Recursive Approach

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].

Code:

class Solution {
    public:
    // Recursive function to solve the Unbounded Knapsack problem
    int maximizeValue(vector<int>& weights, vector<int>& values, int totalItems, int currentIndex, int remainingCapacity) {
        // Base Case 1: If the remaining capacity is 0, no more value can be added
        if (remainingCapacity == 0) {
            return 0;
        }
        // Base Case 2: If we have considered all items, stop the recursion
        if (currentIndex >= totalItems) {
            return 0;
        }

        // Case 1: Include the current item (only if its weight is within the remaining capacity)
        int includeValue = 0;
        if (weights[currentIndex] <= remainingCapacity) {
            includeValue = values[currentIndex] + 
                           maximizeValue(weights, values, totalItems, currentIndex, remainingCapacity - weights[currentIndex]);
        }

        // Case 2: Exclude the current item and move to the next item
        int excludeValue = maximizeValue(weights, values, totalItems, currentIndex + 1, remainingCapacity);

        // Return the maximum of the two cases
        return max(includeValue, excludeValue);
    }

    // Public function to initiate the recursive process for Unbounded Knapsack
    int unboundedKnapsack(vector<int>& weights, vector<int>& values, int totalItems, int capacity) {
        return maximizeValue(weights, values, totalItems, 0, capacity);
    }
};

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 up to N.

2️⃣ Memoization

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 encountered 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.

Code:

class Solution {
public:
    // Recursive function with memoization to solve the Unbounded Knapsack problem
    int maximizeValue(vector<int>& weights, vector<int>& values, int totalItems, int currentIndex, int remainingCapacity, vector<vector<int>>& memo) {
        // Base Case 1: If the remaining capacity is 0, no more value can be added
        if (remainingCapacity == 0) {
            return 0;
        }
        // Base Case 2: If we have considered all items, stop the recursion
        if (currentIndex >= totalItems) {
            return 0;
        }

        // Check if the result is already computed
        if (memo[currentIndex][remainingCapacity] != -1) {
            return memo[currentIndex][remainingCapacity];
        }

        // Case 1: Include the current item (only if its weight is within the remaining capacity)
        int includeValue = 0;
        if (weights[currentIndex] <= remainingCapacity) {
            includeValue = values[currentIndex] + 
                           maximizeValue(weights, values, totalItems, currentIndex, remainingCapacity - weights[currentIndex], memo);
        }

        // Case 2: Exclude the current item and move to the next item
        int excludeValue = maximizeValue(weights, values, totalItems, currentIndex + 1, remainingCapacity, memo);

        // Store the result in the memo table and return
        return memo[currentIndex][remainingCapacity] = max(includeValue, excludeValue);
    }

    // Public function to initiate the recursive process for Unbounded Knapsack
    int unboundedKnapsack(vector<int>& weights, vector<int>& values, int totalItems, int capacity) {
        vector<vector<int>> memo(totalItems, vector<int>(capacity + 1, -1));
        return maximizeValue(weights, values, totalItems, 0, capacity, memo);
    }
};

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.

3️⃣ Tabulation (Bottom-up Approach)

Code:

class Solution
{
public:
    int unboundedKnapsack(vector<int>& wt, vector<int>& val, int n, int W) {

        // Step 1: Create a DP table
        // t[i][j] will store the maximum value we can achieve with the first i items and capacity j
        vector<vector<int>> t(n + 1, vector<int>(W + 1, 0));

        // Step 2: Fill the table
        // Outer loop for items (1 to n)
        for (int item = 1; item <= n; item++) {
            // Inner loop for all capacities (1 to W)
            for (int capacity = 1; capacity <= W; capacity++) {
                
                // Step 3: Exclude the current item
                // Take the value from the previous item (upper row)
                int exclude = t[item - 1][capacity];

                // Step 4: Include the current item (only if weight <= capacity)
                // Since this is unbounded, we can reuse the same item → stay on the same row
                int include = 0;
                if (wt[item - 1] <= capacity) {
                    include = val[item - 1] + t[item][capacity - wt[item - 1]];
                }

                // Step 5: Take the maximum of include and exclude
                t[item][capacity] = max(include, exclude);
            }
        }

        // Step 6: Return the maximum value achievable with 'n' items and total capacity 'W'
        return t[n][W];
    }
};

Complexity Analysis:

• Time Complexity:O(n * W)
• Space Complexity:O(n * W)

4️⃣ Space Optimized Approach (2 Arrays)

We are only using the the last row in the tabulation so instead of storing the data in table we just make use of last row.

Code:

class Solution
{
public:
    int unboundedKnapsack(vector<int>& wt, vector<int>& val, int n, int W) {

        // Step 1: Create a 1D DP array to hold the previous row (initially all 0)
        // prev[j] stores max value for weight j after processing i-1 items
        vector<int> prev(W + 1, 0);

        // Step 2: Iterate through each item
        for (int index = 1; index <= n; index++) {

            // Create a new row (current DP values for item 'index')
            vector<int> curr(W + 1, 0);

            // Step 3: Try all possible capacities from 1 to W
            for (int capacity = 1; capacity <= W; capacity++) {
                
                // Exclude the current item: take value from previous row
                int exclude = prev[capacity];

                // Include the current item (only if it fits in the knapsack)
                // Stay on the same row (curr) since the item is unbounded
                int include = 0;
                if (wt[index - 1] <= capacity) {
                    include = val[index - 1] + curr[capacity - wt[index - 1]];
                }

                // Step 4: Store the max value by including or excluding
                curr[capacity] = max(include, exclude);
            }

            // Step 5: Update prev to current for the next iteration
            prev = curr;
        }

        // Step 6: Return the answer - max value for full capacity W
        return prev[W];
    }
};

Complexity Analysis:

• Time Complexity:O(n * W)
• Space Complexity:O(2W)