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

What is good code?

Recursion

Inside Distributed Systems

Distributed Planets with different roles

What is it like to be a part of Start.ng and HNG?

Java Collections: Under the hood — Stack

Installing Tensorflow on Windows 10 ( GPU Support)- Step by Step

Binomial Distribution and Binomial Test in Python — Statistics — PyShark

COVID-19 Test Reporting using R

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

Minimum Operations to Reduce X to Zero — LeetCode

Leetcode Solutions — 2Sums

The Blind 75 Leetcode Series: Valid Parentheses

Minimum Moves to Reach Target Score