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

Sample Input:

3 15
7 2 4
5 10 20

Sample Output:

21

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.

Approach :

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)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.