Knapsack Problems

You have a fixed capital budget and a list of trade ideas, each with a required capital outlay and an expected payoff. Which subset of ideas maximizes total payoff without exceeding the budget? This is the knapsack problem, and it's a genuinely useful mental model for capital-constrained selection problems, not just a textbook exercise.

The idea: a table indexed by items considered and capacity used

In the 0/1 knapsack (each item taken at most once), define $dp[i][c]$ as the best achievable value using only the first $i$ items with capacity budget $c$. For each item, you have exactly two choices: skip it, keeping $dp[i-1][c]$, or take it (if it fits), gaining its value plus the best you could do with the remaining capacity using only earlier items — $\text{value}_i + dp[i-1][c - \text{weight}_i]$. The recurrence takes the better of the two:

$$dp[i][c] = \max\big(dp[i-1][c],\ \ \text{value}_i + dp[i-1][c - \text{weight}_i]\big)$$

In words: either this item isn't worth its cost given what's left, or it is, and the recurrence checks both possibilities and keeps the winner. Time and space are $O(n \cdot C)$ where $C$ is the capacity — polynomial in the capacity's value, not its number of digits, which is why knapsack is only "efficient" for moderate budgets, not for a budget of, say, $10 billion in cent-sized units.

The unbounded knapsack (unlimited copies of each item — think a bond you can buy in unlimited size) drops the "$i-1$" on the take-branch, since reusing the same item is now allowed: $dp[c] = \max(dp[c],\ \text{value}_i + dp[c - \text{weight}_i])$, iterating capacity forward instead of backward.

Worked example

Budget 5. Items: (weight 2, value 3), (weight 3, value 4), (weight 4, value 5). Building $dp[i][c]$ for $c=0..5$: with only item 1 ($w{=}2,v{=}3$), row is [0,0,3,3,3,3]. Adding item 2 ($w{=}3,v{=}4$): at $c{=}5$, skip gives 3 (previous row), take gives $4 + dp_{\text{row1}}[5-3=2] = 4+3=7$ — take wins, so $dp[2][5]=7$ (items 1 and 2, weight $2+3=5$, value $3+4=7$). Adding item 3 ($w{=}4,v{=}5$) at $c{=}5$: skip gives 7, take gives $5 + dp_{\text{row2}}[5-4=1]=5+0=5$ — skip wins. Final answer: 7, using items 1 and 2.

def knapsack_01(weights, values, capacity):    # O(n * capacity)
    n = len(weights)
    dp = [0] * (capacity + 1)
    for i in range(n):
        for c in range(capacity, weights[i] - 1, -1):   # reverse: 0/1, no reuse
            dp[c] = max(dp[c], values[i] + dp[c - weights[i]])
    return dp[capacity]

Where it shows up

Interview staples: partition equal subset sum, coin change (unbounded knapsack), target sum. On a desk, knapsack-style reasoning appears in capital-constrained trade selection — picking which positions to hold under a margin or capital budget to maximize expected P&L — and in bin-packing-adjacent problems like allocating a fixed risk budget across strategies with different capacity requirements and expected returns.