0-1 Knapsack Problem | Dataford Interview Questions

Belvedere Trading's strategy simulator evaluates candidate strategies with different capital requirements and modeled returns. Given a fixed capital budget, select a subset of strategies that maximizes total modeled return.

Each strategy can be selected at most once. Return the maximum total value achievable without exceeding the budget.

Formal Specification

Implement maximize_value(weights, values, capacity):

weights is a list of integers where weights[i] is the capital required by strategy i.
values is a list of integers where values[i] is the modeled return from strategy i.
capacity is the maximum total capital available.
Return an integer representing the maximum achievable total value.

The lists have equal length, and every strategy is optional.

Constraints

1 <= len(weights) == len(values) <= 200
1 <= weights[i] <= 10^4
0 <= values[i] <= 10^6
0 <= capacity <= 10^4
Each strategy may be selected at most once

Function Signature

def maximize_value(weights, values, capacity):

Your question is 0-1 Knapsack Problem. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem