Last Updated: 5 Mar, 2021
Unbounded Knapsack
Moderate
Asked in companies
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.
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.
Approaches
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 ).
- If ‘N’-th item is included
In the recursive approach, some problems are solved again and again.
Let us see a recursion tree for ‘W’ =7, ‘N’ = 4 , 'PROFIT' =[1,6,10,16], ‘WEIGHT’ = [1,2,3,5].
It is clear from the recursion tree that the problem for ‘N’ = 1 and ‘W’ = 5 is solved for two times.
The recursive approach can be optimized by maintaining an extra 2-d array ‘RES’ that stores the result of the recursive calls. For every sub-problem, we first check the 'RES' array. If the value is already computed we simply return it otherwise we calculate it using recursion and put it in the “res” array.
Algorithm
- Initialize a 2-D array ‘RES’ of ‘ W+1’ rows and ‘N + 1’ columns and initialize its values to -1.
- If ( RES [ W ][ N ] ! = -1 ), return RES [ W ][ N ].
- If ( N == 0 | | W == 0 ) return res [ W ][ N ] = 0.
- If ( W [ N - 1 ] > W )
- RES [ W ][ N ] = UNBOUNDED_KNAPSACK( N - 1, W, profit, weight ).
- Else
- RES [ W ][ N ] = max ( ( Profit [ N - 1 ] + UNBOUNDED_KNAPSACK( N, W - weight [ N - 1 ] , profit, weight ) UNBOUNDED_KNAPSACK( N - 1, W, profit, weight ) ).
- Return res [ W ][ N ].
We will solve the problem in a bottom-up manner. We will compute the result for all values of knapsack capacity from 0 to W. We will maintain a 1-D array ‘DP’ of size ‘W+1’ with all its initial values as 0. ‘DP[ i ]’ stores the maximum profit that can be obtained by using all items and knapsack capacity ‘ i ‘.
For every value of ‘ i ‘, we will check for all items. If the weight of any item at index ‘ j ’ say ‘WEIGHT[ j ]’ is smaller than current knapsack capacity i.e ‘ i ’, that means we can include that item, and ‘DP[ i ]’ will be max ( DP[ i ], PROFIT [ j ] + profit when knapsack capacity = i - WEIGHT[ j ].)
DP [ W ] will store the required answer.
Algorithm
- Initialize a 1-D array ‘DP’ of size ‘W+1’ with all values = 0.
- Run two loops
- ‘i’ : 0 to ‘W’
- ‘j’ : 0 to ‘N-1’
- If ( ‘WEIGHT [ j ]’ < = i ) , DP [ i ] = max (DP [ i ] , PROFIT [ j ] + DP[ i - WEIGHT[ j ] )
- Return DP[ W ].
Similar problems