Statement

Suppose you have a list of weights and corresponding values for nn items. Each item will have a weight and a certain value associated with it. You have a knapsack that can carry items up to a specific maximum weight, known as the capacity of the knapsack.

You want to maximize the sum of values of the items in your knapsack while ensuring that the sum of the weights of the items remains less than or equal to the knapsack’s capacity. If all the combinations exceed the given knapsack’s capacity, return 00.

Note: This problem is an extension of 0/1 Knapsack, so it has slightly different constraints. The main difference here is that you have an infinite supply of each of the nn items. In simpler words, while adding the items to the knapsack, you either add the complete item as many times as you want or don’t add it.

Let’s say you have a knapsack of capacity 1010 and lists of weights and values for 33 items as follows:

items = [x,y,z][x, y, z]

weights = [2,4,6][2, 4, 6]

values = [5,11,13][5, 11, 13]

Considering each item can be used an infinite number of times, there are many ways of storing items in the knapsack, such that the combined weight of stored items is less than or equal to the knapsack’s capacity. Let's see a few of them:

  • Adding only xx five times makes a total weight of 1010, which is within the knapsack's capacity and a total value of 2525:

    • total weight = 2+2+2+2+2=102 + 2 + 2 + 2 + 2 = 10

    • total value = 5+5+5+5+5=255+5+5+5+5=25

  • Adding xx a single time and yy two times makes a total weight of 1010, which is within the knapsack's capacity and a total value of 2727:

    • total weight = 2+4+4=102+4+4=10

    • total value = 5+11+11=275+11+11=27

  • Adding both yy and zz a single time makes a total weight of 1010, which is within the knapsack's capacity and a total value of 2424:

    • total weight = 4+6=104+6=10

    • total value = 11+13=2411+13=24

Though all of the combinations described above are valid, we need to select the one with the maximum total value. Therefore, we will select three items with weights 22, 44, and 44 respectively, since they give us the maximum total value of 2727, without exceeding the capacity of the knapsack, 1010.

Constraints:

  • 11≤ capacity 104≤10^4

  • 11≤ values.length 1500≤1500

  • weights.length ==== values.length

  • 11≤ values[i] 104≤10^4

  • 11≤ weights[i] capacity

Examples

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.