0/1 Knapsack Problem: Dynamic Programming Step by Step

You have a bag that holds a fixed weight and a pile of items, each with a weight and a value. Pick the items that fit and are worth the most. Each item is either in the bag or not — the "0/1" — so you cannot take half of one. It is the dynamic programming problem that most other "choose a subset under a budget" problems turn into.

The problem it solves

Given weights, values and a capacity cap, find the largest total value of a set of items whose total weight is at most cap. The same shape hides in many problems: choosing features for a release within a time budget, picking ads for a fixed slot, deciding whether a subset of numbers sums to a target (that one is knapsack with values equal to weights).

Trying every subset works, but there are 2ⁿ of them. Thirty items already means over a billion subsets.

The intuition

Look at the last item and ask the only question that matters: is it in the best bag or not?

• Leave it out: the answer is the best you can do with the other items and the same capacity.
• Take it (only if it fits): its value, plus the best you can do with the other items and the capacity that is left.

The better of the two is the answer. Both options ask the same kind of question about a smaller problem — fewer items, and possibly less capacity — so the answers can be stored in a table. best[i][c] means "the most value using only the first i items, with capacity c". Row 0 is all zeros (no items, no value), and each row is filled from the one above it.

The table also explains why a greedy rule fails. Sorting by value per kilo and grabbing the best ratios feels right, but a high-ratio item can use up space that two slightly worse items would have filled completely. The table does not guess; it compares both choices at every capacity.

Watch it run

The animation uses the lesson's drone with an 8 kg payload and three items: 3 kg worth 30, 4 kg worth 50 and 5 kg worth 60. Each row adds one item and sweeps the capacities from 8 down to the item's weight, comparing "leave it" with "take it". The final cell reads 90: the 3 kg and 5 kg items fill the bag exactly, and the 4 kg kit — the best single item per kilo — is left behind.

The code

The full table, plus a walk back through it to recover which items were chosen, and the one-row version:

def knapsack_table(weights, values, cap):
    n = len(weights)
    best = [[0] * (cap + 1) for _ in range(n + 1)]   # best[i][c]: first i items, capacity c
    for i in range(1, n + 1):
        w, v = weights[i - 1], values[i - 1]
        for c in range(cap + 1):
            best[i][c] = best[i - 1][c]                 # leave item i-1 behind
            if w <= c:
                best[i][c] = max(best[i][c], best[i - 1][c - w] + v)   # or take it
    chosen, c = [], cap                                 # walk back to find the items
    for i in range(n, 0, -1):
        if best[i][c] != best[i - 1][c]:                # value changed: item was taken
            chosen.append(i - 1)
            c -= weights[i - 1]
    return best[n][cap], chosen[::-1]

def knapsack(weights, values, cap):
    best = [0] * (cap + 1)
    for w, v in zip(weights, values):
        for c in range(cap, w - 1, -1):                 # backwards: each item once
            best[c] = max(best[c], best[c - w] + v)
    return best[cap]

def knapsack_forward(weights, values, cap):             # the bug: forwards
    best = [0] * (cap + 1)
    for w, v in zip(weights, values):
        for c in range(w, cap + 1):
            best[c] = max(best[c], best[c - w] + v)
    return best[cap]

weights, values = [3, 4, 5], [30, 50, 60]
print(knapsack_table(weights, values, 8))                        # (90, [0, 2])
print(knapsack(weights, values, 8), knapsack_forward(weights, values, 8))   # 90 100

The one-row version keeps only the previous row, overwritten in place. That works only if, when best[c] is updated, best[c - w] still holds the value from the previous item. Going from high capacity to low guarantees it: c - w is smaller than c, so it has not been touched yet. Going forwards, best[c - w] may already include the current item, so the item gets packed twice. That is exactly what the forward version does: it returns 100, two copies of the 4 kg kit. (For the unbounded knapsack, where items may repeat, forwards is the correct loop.)

Here is the greedy rule, for comparison:

def greedy_by_ratio(weights, values, cap):
    total = 0
    for w, v in sorted(zip(weights, values), key=lambda p: p[1] / p[0], reverse=True):
        if w <= cap:
            total, cap = total + v, cap - w
    return total

print(greedy_by_ratio(weights, values, 8))              # 80

It takes the 4 kg kit first (12.5 per kilo), then only the 3 kg canister fits: 80, not 90.

To test all of this, a brute force tries every in-or-out pattern of the items. It runs on 2,000 random instances with up to ten items. The check also confirms that the recovered items really fit and really add up to the best value:

import itertools, random

def brute(weights, values, cap):                        # every subset of items
    best = 0
    for picks in itertools.product([0, 1], repeat=len(weights)):
        w = sum(p * x for p, x in zip(picks, weights))
        if w <= cap:
            best = max(best, sum(p * x for p, x in zip(picks, values)))
    return best

random.seed(9)
ok, forward_wrong, greedy_wrong = True, 0, 0
for _ in range(2000):
    n = random.randint(0, 10)
    ws = [random.randint(1, 12) for _ in range(n)]
    vs = [random.randint(1, 40) for _ in range(n)]
    cap = random.randint(0, 30)
    truth = brute(ws, vs, cap)
    value, chosen = knapsack_table(ws, vs, cap)
    ok &= value == truth == knapsack(ws, vs, cap)
    ok &= sum(ws[i] for i in chosen) <= cap and sum(vs[i] for i in chosen) == truth
    forward_wrong += knapsack_forward(ws, vs, cap) != truth
    greedy_wrong += greedy_by_ratio(ws, vs, cap) != truth
print(ok, forward_wrong, greedy_wrong)                  # True 1387 292

Both DP versions match the brute force everywhere. The forward loop is wrong on 1,387 of 2,000 instances and the greedy rule on 292 — often enough to fail any test suite.

The complexity

The table has (n + 1) × (cap + 1) cells and each takes O(1), so time is O(n · cap). Space is the same for the full table, or O(cap) for the one-row version — but the one-row version cannot recover the chosen items without extra bookkeeping.

O(n · cap) looks polynomial, but it depends on the value of cap, not on how many digits it has. A capacity of a billion makes the table unusable. This is called pseudo-polynomial time, and it is why knapsack is still NP-hard in general.

Where it goes wrong

• Looping forwards in the one-row version. It silently turns 0/1 knapsack into unbounded knapsack.
• Trusting value per kilo. Greedy by ratio is optimal only for the fractional knapsack, where items can be split.
• Off-by-one on item index. Row i refers to item i - 1. Adding a zero row at the top keeps the recurrence clean.
• Huge capacities. If cap is large and n is small, enumerate subsets or switch to a table indexed by value instead.

How to say it in an interview

"For each item I either leave it out, giving the best for the remaining items at the same capacity, or take it if it fits, giving its value plus the best at the reduced capacity. I fill a table best[i][c] row by row. That's O(n · cap) time. To save space I use one row and sweep capacity backwards, so each item is counted once. Greedy by value per weight fails here because items can't be split."

The same take-or-leave table appears in partition equal subset sum, and the forward loop is the right one in unbounded knapsack.