DSA Recovering the Knapsack's Contents

The problem

Knapsack traceback recovers which items a knapsack solution chose, not just the best value it reached. Each item has a weight and a value. The bag has one capacity, and each item is taken at most once.

The answer is a pair. The pair holds the best value and the list of chosen item indices. The cases below are the two knapsacks the article solves and reads back.

cases = [
    ([(2, 3), (3, 4), (4, 5)], 5, (7, [0, 1])),
    ([(1, 2), (4, 5), (3, 4), (2, 3)], 6, (9, [0, 2, 3])),
]
for items, cap, expected in cases:
    print("items", items, "capacity", cap, "answer:", expected)

Read the items as weight, value pairs. In the first row, items 0 and 1 weigh 5 together and score 7. No other fitting set scores more.

Intuition: the best value alone forgets the choices

The fast one-row knapsack prints a best value and nothing else. The value is correct. The packing that earned it is gone, because each row overwrote the last.

def value_only(items, cap):
    table = [0] * (cap + 1)
    for w, v in items:
        for c in range(cap, w - 1, -1):
            table[c] = max(table[c], table[c - w] + v)
    return table[cap]

items = [(2, 3), (3, 4), (4, 5)]
print("best value:", value_only(items, 5))
print("chosen items: not stored anywhere")

A reader who must pack the real bag needs the items. Keeping one row per item prefix preserves the history, and walking that history backwards recovers the packing. The next sections build both halves.

Brute force: try every subset and keep the best packing

The brute force lists every subset of items. Each subset is weighed and scored. The best fitting subset is kept whole, items included. A counter records the subsets tried.

def brute_knapsack(items, cap):
    n = len(items)
    tried = 0
    best_value = 0
    best_set = []
    for mask in range(1 << n):
        tried += 1
        weight = 0
        value = 0
        chosen = []
        for i in range(n):
            if mask >> i & 1:
                weight += items[i][0]
                value += items[i][1]
                chosen.append(i)
        if weight <= cap and value > best_value:
            best_value = value
            best_set = chosen
    return best_value, best_set, tried

print(brute_knapsack([(2, 3), (3, 4), (4, 5)], 5))
print(brute_knapsack([(1, 2), (4, 5), (3, 4), (2, 3)], 6))

Both answers match the cases. The subset count doubles with each added item, so the method dies on long item lists even though it hands back the packing for free.

The optimal solution: a full table, then a backward walk

The full table keeps one row per item prefix, where a row entry holds the best value using only the items up to that row within one capacity. That history is the whole state.

The walk starts at the last row and the full capacity. A value equal to the row above means the item was skipped. A changed value means the item was taken, and its weight leaves the remaining capacity.

def solve(items, cap):
    n = len(items)
    table = [[0] * (cap + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w, v = items[i - 1]
        for c in range(cap + 1):
            table[i][c] = table[i - 1][c]
            if w <= c:
                table[i][c] = max(table[i][c], table[i - 1][c - w] + v)
    chosen = []
    c = cap
    for i in range(n, 0, -1):
        if table[i][c] != table[i - 1][c]:
            chosen.append(i - 1)
            c -= items[i - 1][0]
    chosen.reverse()
    return table[n][cap], chosen

cases = [
    ([(2, 3), (3, 4), (4, 5)], 5, (7, [0, 1])),
    ([(1, 2), (4, 5), (3, 4), (2, 3)], 6, (9, [0, 2, 3])),
]
for items, cap, expected in cases:
    result = solve(items, cap)
    print("capacity", cap, "->", result, "expected:", expected, "match:", result == expected)

Every case matches the brute force. The table costs more memory than the one-row method, and the backward walk is the receipt for that memory.

Walkthrough: reading the first knapsack backwards

The walk uses items 2/3, 3/4 and 4/5 at capacity 5. The table prints first. The backward steps print after it, one item at a time.

items = [(2, 3), (3, 4), (4, 5)]
cap = 5
n = len(items)
table = [[0] * (cap + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    w, v = items[i - 1]
    for c in range(cap + 1):
        table[i][c] = table[i - 1][c]
        if w <= c:
            table[i][c] = max(table[i][c], table[i - 1][c - w] + v)
for i, row in enumerate(table):
    print("row", i, row)
chosen = []
c = cap
for i in range(n, 0, -1):
    if table[i][c] != table[i - 1][c]:
        print("item", i - 1, "taken: value", table[i - 1][c], "->", table[i][c], "capacity left", c - items[i - 1][0])
        chosen.append(i - 1)
        c -= items[i - 1][0]
    else:
        print("item", i - 1, "skipped: value stays", table[i][c])
chosen.reverse()
print("chosen:", chosen, "best value:", table[n][cap])

Item 2 is skipped first, because the value at full capacity matches the row above. Items 1 and 0 then show changed values, and each change subtracts that item's weight from the capacity the walk still holds.

Complexity

The table fills one cell per item and capacity pair, so the time is O(n times capacity) for n items. The full table is kept for the walk, so the space is also O(n times capacity), and the walk itself takes O(n) steps.

for n, cap in [(3, 5), (6, 10), (10, 20)]:
    print("items", n, "capacity", cap, "- subsets:", 2 ** n, " table cells:", (n + 1) * (cap + 1))

At ten items the subset search tries 1024 sets against 231 table cells. The gap grows with every added item.

Edge cases and pitfalls

Capacity zero takes nothing. An item heavier than the capacity is skipped by every row and by the walk. An empty item list answers value zero with an empty packing.

Ties are the subtle case. Two different packings can share the best value, and the walk returns one of them, fixed by the rule that an unchanged value means skipped. The article never claims the returned packing is the only best one.

def solve(items, cap):
    n = len(items)
    table = [[0] * (cap + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w, v = items[i - 1]
        for c in range(cap + 1):
            table[i][c] = table[i - 1][c]
            if w <= c:
                table[i][c] = max(table[i][c], table[i - 1][c - w] + v)
    chosen = []
    c = cap
    for i in range(n, 0, -1):
        if table[i][c] != table[i - 1][c]:
            chosen.append(i - 1)
            c -= items[i - 1][0]
    chosen.reverse()
    return table[n][cap], chosen

print("capacity zero:", solve([(2, 3), (3, 4)], 0))
print("too heavy:", solve([(9, 50)], 4))
print("no items:", solve([], 5))
print("tie between twins:", solve([(2, 3), (2, 3)], 2))
print("exact fit:", solve([(5, 8)], 5))

The twin row returns the first twin. Both twins give value 3, and the walk's skip rule settles the tie the same way on every run.