Allocate a fixed budget across strategies

Question

You can fund each strategy at most once. Strategy i needs costs[i] of capital and is expected to earn profits[i]. With a total budget, choose a subset that maximizes expected profit without overspending.

costs   = [2, 3, 4]
profits = [3, 4, 5]
budget  = 5
-> 7        # fund strategies 0 and 1: cost 2+3=5, profit 3+4=7

Return the maximum total profit fitting within the budget (0/1 knapsack). Each strategy is all-or-nothing.

Accepted Answer

Let dp[b] be the best profit achievable with exactly b of budget available. Consider strategies one at a time. For each, walk the budget axis downward (from budget to cost) so that each strategy is counted at most once, a forward loop would let you re-fund the same strategy repeatedly. The choice at each budget is "skip this strategy" (dp[b]) versus "fund it" (dp[b - cost] + profit). Tracing the example, after processing all three strategies dp ends as [0, 0, 3, 4, 5, 7], so dp[5] = 7. Time O(n budget), space O(budget). Edge cases: budget 0 or all costs exceeding budget give 0; this assumes i…

Allocate a fixed budget across strategies

Your answer

More Coding questions