Unbounded Knapsack

Posted: 5 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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.

For Example
Let us say we have 'N' = 3 items and a knapsack of capacity 'W' =  10
'PROFIT' = { 5, 11, 13 }
'WEIGHT' = { 2, 4, 6 }

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 i.e ‘27’. Therefore maximum profit = 27.
Input Format
The first line contains a single integer ‘T’ denoting the number of test cases.

The first line of each test contains two integers ‘N’ - number of elements in the array and ‘W’ - Capacity of the knapsack.

The second line of each test case contains profiti - profit of the item at the ‘i-th’ index.

The third line of each test case contains weighti - weight of the item at the ‘i-th’ index
Output Format
For each test case, 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.
Constraints
1 <= T <= 50
1 <= N <= 10^3
1 <= W <= 10^3
1 <= PROFIT[ i ] , WEIGHT[ i ] <= 10^8

Time Limit: 1sec
Approach 1

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 ).
Try Problem