The optimal value is only half the story; traceback recovers the subset that achieves it. The path moves upward through the table, marking rows where an item was taken. This lesson turns the DP value into a concrete certificate.
highlighted = computed this step
Traceback path
The traceback starts at the final cell and follows 4 cells. Why: each step asks whether the current row changed the value.
traceback from final state
Chosen items
The chosen items are item 2 and item 3. Why: those are the rows where traceback takes the item.
chosen items 2,3
Subset certificate
Their total weight is 7, equal to capacity 7, and total value is 9. Why: the chosen subset achieves the table's optimum.
value=9
Scope of DP
This DP table is exact here, but table size grows with item count times capacity magnitude. Why: knapsack DP is pseudo-polynomial, not a small-table guarantee for every encoding.
exact table, pseudo-polynomial size
Diagram note
Purple cells show the traceback path; starred rows mark chosen items. Pixel positions are rounded for layout; every number shown is exact.