Unbounded Knapsack

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
182 upvotes
Asked in companies
AdobeGartnerAmazon

Problem statement

You are given ‘n’ items with certain ‘profit’ and ‘weight’ and a knapsack with weight capacity ‘w’.


You need to fill the knapsack with the items in such a way that you get the maximum profit. You are allowed to take one item multiple times.


Example: 
Input: 
'n' = 3, 'w' = 10, 
'profit' = [5, 11, 13]
'weight' = [2, 4, 6]

Output: 27

Explanation:
We can fill the knapsack as:

1 item of weight 6 and 1 item of weight 4.
1 item of weight 6 and 2 items of weight 2.
2 items of weight 4 and 1 item of weight 2.
5 items of weight 2.

The maximum profit will be from case 3 = 11 + 11 + 5 = 27. Therefore maximum profit = 27.


Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains two integers ‘n’ and ‘w’ - number of items and weight capacity of the knapsack.

The second line of each test case contains 'n' integers - elements of 'profit' array.

The third line of each test case contains 'n' integers - elements of 'weight' array.


Output Format: 
Return an integer denoting the maximum profit that can be obtained by filling the knapsack.


Note: 
You do not need to print anything; it has already been taken care of. Just implement the given function.
Sample Input 1:
3 15
7 2 4
5 10 20


Expected Answer:
21


Output on console:
21


Explanation of Sample Input 1
The given knapsack capacity is 15. We can fill the knapsack as [1, 1, 1] giving us profit 21 and as [1,2] giving us profit 9. Thus maximum profit will be 21.


Sample Input 2
2 3
6 12
4 17


Expected Answer:
0


Output on console:
0


Explanation of Sample Input 2:
We can clearly see that no item has weight less than knapsack capacity. Therefore we can not fill knapsack with any item.


Expected Time Complexity:
Try to solve this in O(n*w).


Constraints
1 <= n <= 10^3
1 <= w <= 10^3
1 <= profit[i] , weight[i] <= 10^8

Time Limit: 1 sec
Hint

Try to find all possible sequences of items using recursion.

Approaches (3)
Recursion

A simple idea is to consider all possible sequence of items that have a total weight not more than ‘W’ and find the subset which gives maximum profit. 

  • For any item at index ‘i’ there will be two choices - either we include the item at least once or we do not include the item.
  • If we do not include the item, we will recursively solve for ‘N-1’ items and knapsack capacity ‘W’.
  • If we include the item, we will recursively solve for ‘N’ items and capacity = ‘W - weight of Nth item’ and add profit of ‘ N-th’ item to its result as we have included that.
  • As we can use any item multiple times, so after including ‘N-th’ item we will still solve for ‘N’ items.
  • The maximum value obtained from all these recursive calls will be the required profit.

 

Algorithm

 

  • Let UNBOUNDED_KNAPSACK( N, W, PROFIT, WEIGHT ) be our recursive function.
  • If no item is left or the capacity of the knapsack is 0 i.e. If ( ‘N’ = 0 or ‘W’ = 0), return 0.
  • If 'WEIGHT[ N - 1]' > ‘W’  i.e if the weight of the Nth item is greater than the knapsack capacity, we can not include the N-th item. Therefore return UNBOUNDED_KNAPSACK( N - 1, W, PROFIT, WEIGHT ).
  • Otherwise, return maximum of the following two values
    • If ‘N’-th item is included
      • ‘PROFIT’ [ N  - 1 ] + UNBOUNDED_KNAPSACK( N, W - WEIGHT [ N - 1 ] , PROFIT, WEIGHT )
    • If N-th item is not included
      • UNBOUNDED_KNAPSACK( N - 1, W, PROFIT, WEIGHT ).
Time Complexity

O(2^N), where ‘N’ is the total number of items.

 

Recursion will lead to exponential time complexity. Therefore time complexity is of order 2^N.

Space Complexity

O(2^N), where ‘N’ is the total number of items.

 

Recursion will lead to exponential calls of the functions which will be store in stack. Therefore space complexity is of order 2^N.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Unbounded Knapsack
Full screen
Console