1152. Unbounded Knapsack — Basic

Given item weights and values and a knapsack capacity, where each item may be used any number of times, maximize the total value without exceeding the capacity. Return that maximum value. The input is JSON {weights, values, capacity}.

Input: JSON {weights, values, capacity}.

Output: Integer — the maximum achievable value.

Examples

Input: {"weights":[1,3,4,5],"values":[1,4,5,7],"capacity":8}
Output: 11
Explanation: Reuse items to fill capacity 8.

Input: {"weights":[3],"values":[5],"capacity":10}
Output: 15
Explanation: Three copies of the item.

Input: {"weights":[2],"values":[3],"capacity":1}
Output: 0
Explanation: Item too heavy.

Constraints

• 1<=n<=100
• 1<=capacity<=1000

Asked by