# 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)