0/1 Knapsack

0/1 Knapsack is the gateway problem for two-dimensional dynamic programming. Each item is either fully taken or fully left behind — there is no taking half of it — and you want the most valuable haul that still fits in a weight-limited bag.

The slow way first

The brute-force idea: for every item decide take-or-skip, so there are 2^n subsets. Try them all, keep the best feasible one. That is O(2^n) — it explodes the moment n passes about 20.

The question to ask: what decision am I really making, and what do I need to know to make it? For each item I choose take or skip, and to compare those two choices I only need the best value I could get with the earlier items at the relevant capacity. That is a subproblem I can remember instead of recomputing.

The idea: a grid of subproblems

Define dp[i][w] = the best total value using only the first i items within capacity w. Build the grid row by row. For each cell there are two choices:

• Skip item i: the value is dp[i-1][w] — same capacity, one fewer item.
• Take item i (only if wt[i] <= w): the value is val[i] + dp[i-1][w - wt[i]] — its value plus the best you could do with the remaining capacity using earlier items.

Keep the larger of the two. The answer is the bottom-right cell, dp[n][W].

The key insight: every cell is decided by exactly two cells in the row directly above it. That is why a single pass over the grid, top to bottom, is enough.

Walk through it

Step through the animation. The grid is (n+1) rows by (W+1) columns; row 0 and column 0 are all zero. For each cell we light up the two cells it reads from the row above — the skip cell straight up, and the take cell up-and-left by the item weight — then store the larger result. When item 1 (weight 1) cannot fit a smaller capacity it just copies the value above; when items fit, the take branch wins and values climb toward the final 45.

Pseudocode

n = number of items
make a grid dp with (n+1) rows and (W+1) columns, all 0
for i from 1 to n:
    for w from 0 to W:
        skip = dp[i-1][w]                       # leave item i out
        if weight of item i <= w:               # does it fit?
            take = val[i] + dp[i-1][w - wt[i]]   # put it in, fill the rest
            dp[i][w] = max(skip, take)           # keep the better choice
        else:
            dp[i][w] = skip                      # too heavy, must skip
return dp[n][W]                                  # best value, all items, full capacity

The Python solution

def knapsack(wt, val, W):
    n = len(wt)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(W + 1):
            skip = dp[i - 1][w]
            if wt[i - 1] <= w:
                take = val[i - 1] + dp[i - 1][w - wt[i - 1]]
                dp[i][w] = max(skip, take)
            else:
                dp[i][w] = skip
    return dp[n][W]

• dp[i][w] is the best value using the first i items within capacity w; the extra row and column of zeros mean no items or no capacity.
• skip = dp[i - 1][w] is the value if we leave item i out — read the same column one row up.
• wt[i - 1] <= w is the fit check (the list is 0-indexed, so item i lives at index i - 1).
• take = val[i - 1] + dp[i - 1][w - wt[i - 1]] adds item i value to the best we could do with the leftover capacity w - wt[i - 1] using earlier items.
• dp[i][w] = max(skip, take) keeps the better of the two choices; if the item is too heavy, only skip is possible.
• The final answer is dp[n][W] — all items considered, full capacity available.

Complexity

The DP is pseudo-polynomial: it depends on the numeric capacity W, not just the item count. The grid uses O(n * W) space, which a one-row rolling array can shrink to O(W) by overwriting right-to-left — but the two-row grid is easier to read and to reconstruct which items were chosen.

When this pattern shows up

Practice