Unbounded Knapsack — Asked in Amazon and Google Interview
Problem Statement :
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.
The first line contains two integers ’N’ — number of elements in the array and ‘W’ — Capacity of the knapsack.
The second line contains profit[i] — profit of the item at the ‘i-th’ index.
The third line contains weight[i] — weight of the item at the ‘i-th’ index
7 2 4
5 10 20
Explanation of Sample Test Case:
The given knapsack capacity is 15. We can fill the knapsack as [5, 5, 5] and [10, 5]. We will get a maximum profit of 21.
Bottom Up Approach
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.
The algorithm will be as follows -
Time Complexity : O(N*W)
Space Complexity : O(N)