Unbounded Knapsack

Problem Statement

Given a knapsack weight W and a set of N items with certain values(benefit or profit) val, and weights wt, find the maximum amount that could make up the exact knapsack weight. In Unbounded Knapsack, you may select an item multiple times.

Example

N = 4

W = 10

val[] = {15, 25, 20, 10}

wt[] = {3, 4, 6, 8}

Example Explanation

Therefore to get the best outcome the selected items are : Item number 2, with weight 4 yields a profit of 25. Item number 1, with weight 3 yields a profit of 15. Item number 1, with weight 3 yields a profit of 15.

Therefore total profit using the unbounded knapsack will be $25+15+15 = 55$.

Input/Output

Input

• The first line of input integer N represents the number of items.
• The second line contains an array val of length N that contains values of the items.
• The third line contains an array wt of length N that contains the weights of the items.
• The fourth line contains the integer W which represents the total weight of the knapsack.

Output

The first and only line of the output contains an integer that represents the maximum profit that can be obtained without crossing the weight limit of the knapsack.

Constraints

$1 ~≤ ~N~,~ W ~≤ ~1000$ $1 ~≤ ~val[i]~, ~wt[i] ~≤ ~100$

Algorithm 1 - Brute Force Approach - Recursive Approach

Algorithm

• Step 1 - Begin by calling the recursive function ‘unboundedKnapsack()’ that takes parameters W, index, val, and wt.
• Step 2 - Set the base case that if ‘index’ = 0 or ‘W’ = 0 function returns 0.
• Step 3 - Next, check if the weight of the item at the index is more than the knapsack weight ‘W’.
  • If yes then return the result obtained after recursively calling the ‘unboundedKnapsack()’ function for the remaining elements.
  • Else using the max function return the maximum of the following
    • result obtained by calling the recursive function ‘getMaxVal()’ for ‘index - 1’ and ‘W - weight[index]’.
    • result obtained by calling the recursive function ‘unboundedKnapsack()’ for ‘index - 1’ items with ‘W’ weight.

Code Implementation

C++

Java

Python

Output

Time Complexity

The recursive calls increase at a rate of 2 until ‘N’ or ‘W’ becomes 0, as every function calls itself twice. Thus the maximum possible calls are $2^N$. The overall time complexity for this approach will be $O(2^N)$.

Space Complexity

The recursive approach is based on calculating the total weight and value of all subsets without using any additional data structure. Since no extra space is required the space complexity for this approach will be O(1).

Algorithm 2 - Bottom-Up Approach - Dynamic Programming - Iteration + Tabulation

Algorithm

• Step 1 - Initialize a 2D array ‘dp’ of size $(N + 1) * (W)$ and fill it with -1.
• Step 2 - Call the recursive function ‘unboundedKnapsack()’ that takes parameters W, N, val, and wt.
• Step 3 - To find the maximum profit for every sub-array and every possible Knapsack Weight use dp as a table where:
  • Either exclude the item and consider profit obtained from the sub-array excluding it dp[i - 1][j].
  • Or include the item if weight is lesser than the knapsack weight available val[i] + dp[i][j - wt[i]] and consider the maximum of the two.

Code Implementation

C++

Java

Python

Output

Time Complexity

Since N * W subproblems are considered the overall time complexity for this approach will be O(N * W).

Space Complexity

As a new 2D array 'dp' is being introduced, Therefore, the overall space complexity for this approach will be O(N * W).

Algorithm 3 - Top-down Approach - Dynamic Programming with Memoization

Algorithm

The top-down approach aims at removing duplicate calls by using an array to store the state of ‘N’ and ‘W’.

• Step 1- Initialize a 2D array ‘dp’ of size $(N + 1) * (W)$ and fill it with -1.
• Step 2 - Call the recursive function ‘unboundedKnapsack()’ that takes parameters W, index, val, wt, and dp.
• Step 3 - Set the base case that if ‘index’ = 0 or ‘W’ = 0 function returns 0.
• Step 4- Next, check if the value is present in the array. If yes, then return the value.
• Step 5 - Next, check if the weight of the item at the index is more than the knapsack weight ‘W’.
  • If yes then return the result obtained after recursively calling the ‘unboundedKnapsack()’ function for the remaining elements.
  • Else return the maximum of the following
    • result obtained by calling the recursive function ‘getMaxVal()’ for ‘index - 1’ and ‘W - weight[index]’.
    • result obtained by calling the recursive function ‘unboundedKnapsack()’ for ‘index - 1’ items with ‘W’ weight.

Code Implementation

C++

Java

Python

Output

Time Complexity

Since N * W recursive calls are made the overall time complexity for this approach will be O(N * W).

Space Complexity

As a new 2D array 'dp' is being introduced, the space complexity will be O(N * W). Again, O(N) space is required for the recursive call stack. Therefore, the overall space complexity for this approach will be O(N * W) + O(N).