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:
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 - 1If 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 need | What to keep |
|---|---|
| the value only | one or two rows |
| the value and the choices | the whole table |
| the value, and choices rarely | roll 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.