Unbounded Knapsack

Given item weights, values, and a knapsack capacity, return the maximum value achievable when each item can be chosen unlimited times. This is the standard unbounded knapsack maximization problem.

Input Format

weights = item weights, values = item values, capacity = knapsack capacity

Output Format

maximum total value with unlimited copies allowed

Constraints

• 1 <= n <= 2000; 1 <= weights[i], values[i] <= 10^4; 0 <= capacity <= 10^4

Examples

weights = [2,3,4]
values = [15,20,30]
capacity = 7

50

weights = [1,3,4]
values = [10,40,50]
capacity = 6

80