0/1 Knapsack

#How does it work?

In the 0/1 knapsack problem every item has a weight and a value, and the knapsack can only carry so much weight. Each item is either taken or left (0/1), and the goal is the highest total value.

A greedy approach (e.g. taking the best value-per-weight first) can get it wrong. Trying every subset means 2ⁿ options.

In the DP table, dp[i][c] is the best value using the first i items with capacity c. Each cell has two options: leave item i (dp[i − 1][c]) or, if it fits, take it (dp[i − 1][c − w] + v). The larger one wins.

Once the table is full, walk back from the bottom right: if a cell differs from the one above it, that item was taken.

#Try it yourself

#Step by step

1. 01dp[0][c] = 0: with no items the value is 0.
2. 02For each item i (weight w, value v) and each capacity c: leaving it gives dp[i − 1][c].
3. 03If w ≤ c, taking it gives dp[i − 1][c − w] + v; write the larger of the two to dp[i][c].
4. 04dp[n][W] is the answer; walk back from the bottom right to find the items.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

# (weight, value) of each item.
ITEMS = [(1, 1), (3, 4), (4, 5), (5, 7)]
W = 7

n = len(ITEMS)
# dp[i][c] = best value using the first i items with capacity c.
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    w, v = ITEMS[i - 1]
    for c in range(W + 1):
        dp[i][c] = dp[i - 1][c]  # skip item i
        if w <= c:
            dp[i][c] = max(dp[i][c], dp[i - 1][c - w] + v)  # or take it

# Walk back: a value that differs from the row above means item i was taken.
taken, c = [], W
for i in range(n, 0, -1):
    if dp[i][c] != dp[i - 1][c]:
        taken.append(i)
        c -= ITEMS[i - 1][0]

print(dp[n][W])
print(" ".join(map(str, reversed(taken))))  # 1-based item numbers

#Complexity

n is the number of items and W the capacity. O(n · W) looks polynomial but depends on the numeric value of W (pseudo-polynomial): a huge capacity means a huge table. With a single row, iterating capacities from high to low, memory drops to O(W).

#When to use it?

"Pick the most value within a limited capacity" problems: budgeting and resource allocation, portfolio selection, cargo loading, choosing topics to study before an exam. The same table idea powers subset sum and coin-change problems.

#Practice

Log in to answer questions and save your progress.

#Up next

Lessons that build on this one:

• Coin Change
• Fractional Knapsack