# 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 157 2 45 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.

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

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

--

--

--

## More from Placewit

Upskilling students for tech placements!

Love podcasts or audiobooks? Learn on the go with our new app.

## Placewit

Upskilling students for tech placements!