775. Knapsack 0/1 (Recursive + Memoization)

Given integer arrays weights and values of equal length n (where weights[i] and values[i] describe the i-th item) and a non-negative integer capacity W, return the MAXIMUM total value attainable by selecting a subset of items such that the total weight does not exceed W. Each item may be taken AT MOST ONCE (0/1 Knapsack). Implement with recursion + memoization.

Input is a JSON object: {"weights": [...], "values": [...], "W": cap}.

Input: A JSON object with weights, values, W.

Output: Return an integer — the maximum attainable value.

Examples

Input: {"weights":[1,3,4,5],"values":[1,4,5,7],"W":7}
Output: 9
Explanation: Take items 1 and 2: weights 3+4=7, values 4+5=9.

Input: {"weights":[1],"values":[5],"W":0}
Output: 0
Explanation: Zero capacity -> nothing can be taken.

Input: {"weights":[5],"values":[10],"W":4}
Output: 0
Explanation: Item too heavy to fit.

Constraints

• 1 <= n <= 8
• 1 <= weights[i], values[i] <= 1000
• 0 <= W <= 100

Asked by