DSA 0/1 Knapsack

The problem

0/1 Knapsack packs items into a bag with a weight limit to gain the most total value. Each item is taken at most once, and the name records that choice as 1 for taken or 0 for left.

Every item has a weight and a value. The total weight of the taken items must stay within the capacity. The answer is the largest total value that fits, with the items that earn it.

first = [("rope", 2, 3), ("lamp", 3, 4), ("book", 4, 5), ("boots", 5, 6)]
second = [("tent", 4, 7), ("stove", 3, 5), ("pack", 5, 8), ("rope", 2, 3)]
cases = [
    (first, 5, 7),
    (second, 7, 12),
    (first, 0, 0),
    ([("boulder", 10, 100)], 5, 0),
]
for items, capacity, expected in cases:
    print("items:", items)
    print("capacity", capacity, "best value:", expected)

Read the first case by hand. The rope and the lamp weigh 5 together and give value 7. The boots alone give 6 and the book alone gives 5, so the pair wins.

Intuition: best value per weight fails

The first idea ranks items by value per unit of weight. It packs the best ratio first while space remains. A high-ratio item can still block the space that a better load needs.

items = [("crate", 5, 6), ("jar", 3, 4), ("tin", 3, 4)]
capacity = 5
ranked = sorted(items, key=lambda item: item[2] / item[1], reverse=True)
load = []
room = capacity
for name, weight, value in ranked:
    if weight <= room:
        load.append(name)
        room -= weight
total = sum(value for name, weight, value in items if name in load)
print("greedy load:", load, "value:", total)
print("crate alone value:", 6)

The greedy load earns 4. The crate alone earns 6 in the same bag. Ratio order packed the jar first and never reconsidered it, and the tin no longer fit beside it.

Brute force: test every subset

The brute force tests every subset of items. It adds the weights and the values of each subset. Subsets over the capacity are thrown away, and the best value among the rest wins.

items = [("rope", 2, 3), ("lamp", 3, 4), ("book", 4, 5), ("boots", 5, 6)]
capacity = 5
checked = 0
best = 0
chosen = []
for mask in range(2 ** len(items)):
    checked += 1
    group = [items[i] for i in range(len(items)) if mask & (1 << i)]
    weight = sum(item[1] for item in group)
    value = sum(item[2] for item in group)
    if weight <= capacity and value > best:
        best = value
        chosen = [item[0] for item in group]
print("subsets checked:", checked)
print("best value:", best)
print("chosen:", chosen)

Four items give 16 subsets. Each added item doubles the subset count. The table method in the next section answers the same question cell by cell instead.

The optimal solution: best value for the first i items at each capacity

The state is best(i, c), the most value that the first i items can give within capacity c. That one sentence is the whole method.

Each cell chooses the larger of two options. Skipping the item keeps the answer from the row above. Taking it adds its value to the best answer at the smaller capacity in the row above. Every cell reads the row above only, so no item can enter a load twice.

def knapsack(items, capacity):
    n = len(items)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        name, weight, value = items[i - 1]
        for c in range(capacity + 1):
            skip = dp[i - 1][c]
            take = -1
            if weight <= c:
                take = value + dp[i - 1][c - weight]
            dp[i][c] = max(skip, take)
    chosen = []
    c = capacity
    for i in range(n, 0, -1):
        if dp[i][c] != dp[i - 1][c]:
            chosen.append(items[i - 1][0])
            c -= items[i - 1][1]
    chosen.reverse()
    return dp[n][capacity], chosen

first = [("rope", 2, 3), ("lamp", 3, 4), ("book", 4, 5), ("boots", 5, 6)]
second = [("tent", 4, 7), ("stove", 3, 5), ("pack", 5, 8), ("rope", 2, 3)]
cases = [
    (first, 5, 7),
    (second, 7, 12),
    (first, 0, 0),
    ([("boulder", 10, 100)], 5, 0),
]
for items, capacity, expected in cases:
    best, chosen = knapsack(items, capacity)
    print("capacity", capacity, "-> best", best, "expected:", expected, "match:", best == expected, "chosen:", chosen)

All four cases match. Capacity zero takes nothing. The boulder never fits, so its large value is never counted.

Walkthrough: the table for capacity 5

The walk fills the table for the first item set at capacity 5. Each printed row is the table after one more item becomes available. The first row allows no items at all.

items = [("rope", 2, 3), ("lamp", 3, 4), ("book", 4, 5), ("boots", 5, 6)]
capacity = 5
n = len(items)
dp = [[0] * (capacity + 1)]
print("no items:", dp[0])
for i in range(n):
    name, weight, value = items[i]
    row = [0] * (capacity + 1)
    for c in range(capacity + 1):
        skip = dp[i][c]
        take = -1
        if weight <= c:
            take = value + dp[i][c - weight]
        row[c] = max(skip, take)
    dp.append(row)
    print("after", name, ":", row)
chosen = []
c = capacity
for i in range(n, 0, -1):
    if dp[i][c] != dp[i - 1][c]:
        chosen.append(items[i - 1][0])
        c -= items[i - 1][1]
chosen.reverse()
print("best value:", dp[n][capacity])
print("chosen:", chosen)

The last cell of the last row holds 7. Walking backward, the lamp row is where the value at capacity 5 changed, and the rope row is where it changed again at capacity 2. Those two changes name the chosen items.

Complexity

Time is O(items times capacity). The table fills one cell for each pair of an item and a capacity.

Space is O(items times capacity) for the full table. The table is kept whole here because the backward walk needs every row. A one-row form uses O(capacity) when only the best value is needed.

def count_cells(item_count, capacity):
    items = [(1, 1)] * item_count
    dp = [[0] * (capacity + 1) for _ in range(item_count + 1)]
    cells = 0
    for i in range(1, item_count + 1):
        weight, value = items[i - 1]
        for c in range(capacity + 1):
            cells += 1
            skip = dp[i - 1][c]
            take = value + dp[i - 1][c - weight] if weight <= c else -1
            dp[i][c] = max(skip, take)
    return cells

for item_count, capacity in [(2, 5), (4, 10), (8, 20)]:
    print("items", item_count, "capacity", capacity, "- cells filled:", count_cells(item_count, capacity))

The cell count is the plain product of items and capacities. It grows steadily in both directions. The subset count of the brute force doubles per item instead.

Edge cases and pitfalls

No items and no capacity both answer 0 with an empty load. An item heavier than the capacity is skipped at every cell, however large its value.

def knapsack(items, capacity):
    n = len(items)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        name, weight, value = items[i - 1]
        for c in range(capacity + 1):
            skip = dp[i - 1][c]
            take = -1
            if weight <= c:
                take = value + dp[i - 1][c - weight]
            dp[i][c] = max(skip, take)
    chosen = []
    c = capacity
    for i in range(n, 0, -1):
        if dp[i][c] != dp[i - 1][c]:
            chosen.append(items[i - 1][0])
            c -= items[i - 1][1]
    chosen.reverse()
    return dp[n][capacity], chosen

first = [("rope", 2, 3), ("lamp", 3, 4), ("book", 4, 5), ("boots", 5, 6)]
print("no items:", knapsack([], 5))
print("no capacity:", knapsack(first, 0))
print("item too heavy:", knapsack([("boulder", 10, 100)], 5))
print("exact fit:", knapsack([("tent", 5, 9)], 5))

The classic mistake compresses the table into one row and scans that row upward. The current item then reads cells it updated itself in the same pass, and one item enters the load many times.

weight = 2
value = 3
up = [0] * 6
for c in range(weight, 6):
    up[c] = max(up[c], up[c - weight] + value)
print("upward row:", up)
down = [0] * 6
for c in range(5, weight - 1, -1):
    down[c] = max(down[c], down[c - weight] + value)
print("downward row:", down)

The upward row claims value 6 at capacity 5, from an item that exists once. That upward scan is a different problem's method, and the next lesson gives it its own article.