Given n items, each with a weight and a value, and a knapsack of capacity W, take each item at most once to maximize the total value without exceeding W. Greedy by value/weight fails here (the 160 versus 220 example from the greedy lesson), so we use DP.

State, transition, base, answer

  • State: dp[i][w] is the best value using the first i items with capacity w.
  • Transition: skip item i (dp[i-1][w]) or take it (dp[i-1][w-weight] + value, if weight <= w) and keep the maximum.
  • Base: dp[0][w] = 0.
  • Answer: dp[n][W].
Knapsack table for four items and capacity 7
Knapsack table for four items and capacity 7

The table in code

python
def knapsack(items, cap):
    n = len(items)
    # dp[i][w]: best value using the first i items with capacity w
    dp = [[0] * (cap + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        weight, value = items[i - 1]
        for w in range(cap + 1):
            dp[i][w] = dp[i - 1][w]                       # skip item i
            if weight <= w:                               # or take it
                dp[i][w] = max(dp[i][w], dp[i - 1][w - weight] + value)
    return dp