# Solving the Unbounded Knapsack Problem

Let's solve the Unbounded Knapsack problem using Dynamic Programming.

## Statement

Suppose you have a list of weights and corresponding values for * *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

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

items =

weights =

values =

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

**Constraints:**

$1≤$ `capacity`

$≤10^4$ $1≤$ `values.length`

$≤800$ `weights.length`

$==$ `values.length`

$1≤$ `values[i]`

$≤10^4$ $1≤$ `weights[i]`

$≤$ `capacity`

## Examples

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