Unbounded Knapsack
Implement unboundedKnapsack
Given a set of items, each with a weight and a value, and a bag with a maximum weight capacity, choose items — each one reusable as many times as it fits — that maximize the total value packed into the bag without exceeding its capacity. Unlike the standard knapsack, any item can be placed in more than once.
Every item still faces a decision at every point, but now that decision is "move on for good" versus "use this item again": moving on keeps the current capacity but permanently rules the item out, while using it again banks its value, spends its weight, and leaves it just as available as before for the leftover capacity. Because an item can contribute any number of times, tracking the best value reachable at every capacity — and letting each item's own update reuse results that already include that same item — captures unlimited reuse without ever explicitly counting how many copies were taken.
Example 1:
Input: weights = [3,4,5], values = [4,5,6], capacity = 6
Output: 8
Example 2:
Input: weights = [2], values = [3], capacity = 7
Output: 9
Example 3:
Input: weights = [5], values = [10], capacity = 3
Output: 0
+ 7 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ weights.length = values.length ≤ 20 - ●
1 ≤ weights[i], values[i] ≤ 100 - ●
0 ≤ capacity ≤ 1000
weights =
[3, 4, 5]
values =
[4, 5, 6]
capacity =
6