Solving the Unbounded Knapsack Problem

Statement

Suppose you have a list of weights and corresponding values for $n$ 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 $0$.

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 $n$ 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 $10$ and lists of weights and values for $3$ items as follows:

items = $[x, y, z]$

weights = $[2, 4, 6]$

values = $[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 $x$ five times makes a total weight of $10$, which is within the knapsack's capacity and a total value of $25$:

  • total weight = $2 + 2 + 2 + 2 + 2 = 10$

  • total value = $5+5+5+5+5=25$

• Adding $x$ a single time and $y$ two times makes a total weight of $10$, which is within the knapsack's capacity and a total value of $27$:

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

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

• Adding both $y$ and $z$ a single time makes a total weight of $10$, which is within the knapsack's capacity and a total value of $24$:

  • total weight = $4+6=10$

  • total value = $11+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 $2$, $4$, and $4$ respectively, since they give us the maximum total value of $27$, without exceeding the capacity of the knapsack, $10$.

Constraints:

• $1≤$ capacity $≤10^4$

• $1≤$ values.length $≤5000$

• weights.length $==$ values.length

• $1≤$ values[i] $≤10^4$

• $1≤$ weights[i] $≤$ capacity

Examples