1145. 0/1 Knapsack — Basic

Given item weights and values and a knapsack capacity, select a subset of items (each used at most once) so their total weight does not exceed the capacity and their total value is maximized. 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":7}
Output: 9
Explanation: Take items of weight 3 and 4.

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

Input: {"weights":[1,2],"values":[10,20],"capacity":3}
Output: 30
Explanation: Take both.

Constraints

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

Asked by