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.

--

--

--

Upskilling students for tech placements!

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

Recommended from Medium

Caching revamp at Goibibo with Aerospike

Subtitle/Caption YouTube Videos with Simon Says

15 Reasons Why I Will Get a Covid-19 Vaccine

Symbolic Decimals Ctflearn

Kubernetes Dashboard

Two Symbol Turing Machine

Convert Spreadsheet Data To Dashboards With DashboardFox LiftOff Service

Advanced Java Tutorial — Learn JDBC, Java Servlets & JSP with Examples

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Placewit

Placewit

Upskilling students for tech placements!

More from Medium

PlatinumX Tech’s Algorithm Expert Course Review (How I got into Turing).

Cross the Bridge Puzzle

Leetcode 862. Shortest Subarray with Sum at Least K

Interview Preparation Series