Skip to content

state 28 of 32 · 5 min

Getting back the answer, not just the number

Your table says the cheapest packing is worth 47. The next question is always "which items?", and the number alone does not say.

Walk back through the table

The table already holds the answer; you just have to read it backwards. Start at the final cell and ask, at each step, which choice produced this value.

For knapsack:

code
i = n, w = W
while i > 0:
    if best[i][w] != best[i - 1][w]:
        item i was taken
        w = w - weight[i]
    i = i - 1

If the value would have been the same without item i, it was not taken. If it differs, it was, and the remaining capacity shrinks accordingly.

This costs O(n) on a table you already built, which is why it is almost always better than the alternative of storing a choice alongside every cell.

The catch, which page five warned about

This only works if the table still exists. Roll it to one row to save memory and the path is gone, because the rows you would have walked back through were thrown away.

So decide before you optimise:

What you needWhat to keep
the value onlyone or two rows
the value and the choicesthe whole table
the value, and choices rarelyroll it, then rebuild fully if asked

Why interviewers ask for it

Because it separates people who have memorised a recurrence from people who understand what the table means. If you can explain that best[i][w] is the answer to a smaller version of the same question, walking backwards is obvious. If the table is a magic square of numbers, it is impossible.