1259. 3D Knapsack — Two Constraints

Each item has a weight, a volume, and a value. Given a weight capacity W and a volume capacity V, select a subset of items (each at most once) so that total weight is at most W and total volume is at most V, maximizing total value. Return that maximum value. The input is JSON {weights, volumes, values, W, V}.

Input: JSON {weights, volumes, values, W, V}.

Output: Integer — the maximum achievable value.

Examples

Input: {"weights":[1,2,3],"volumes":[2,1,3],"values":[10,20,30],"W":4,"V":4}
Output: 30
Explanation: Two items fit both capacities.

Input: {"weights":[5],"volumes":[5],"values":[9],"W":1,"V":1}
Output: 0
Explanation: The item does not fit.

Input: {"weights":[1],"volumes":[1],"values":[7],"W":1,"V":1}
Output: 7
Explanation: Exact fit.

Constraints

• 1<=n<=100
• 1<=W,V<=100

Asked by