Backtracking recovers the decisions behind an optimal value by tracing a completed dynamic-programming table from its final state toward its base cases. Tabulation finds the value; backtracking identifies one set of choices that produces it. section 6.2.6 section 6.2.5
At each state V(i, c), compare its value with the value in the preceding row at the same capacity:
- If V(i, c) is greater than V(i − 1, c), include item i and subtract its weight from the remaining capacity. section 6.2.6
- If the values are equal, exclude item i and continue at the same capacity; another optimal solution may include it. section 6.2.6
- Stop when the remaining capacity reaches zero. section 6.2.6
A knapsack solution
Starting from V(4, 7) = 10, the comparisons include Items 4, 3, and 2, reducing capacity from 7 to 0. Their total weight is 7 and their total value is 10. section 6.2.6
Table 6.6 Backtracking from the optimal value to identify the selected items. Each comparison determines whether the current item was included and, if so, reduces the remaining capacity by its weight.
|
Item (𝑖)
|
(𝑤𝑖, 𝑣𝑖)
|
Start State
|
Comparison
|
Decision
|
Remaining Capacity
|
|
4
|
(1,
2)
|
𝑉(4,
7) = 10
|
10
> 𝑉(3,
7) = 9
|
Include
|
7
– 1 = 6
|
|
3
|
(2,
3)
|
𝑉(3,
6) = 8
|
8
> 𝑉(2,
6) = 5
|
Include
|
6
– 2 = 4
|
|
2
|
(4,
5)
|
𝑉(2,
4) = 5
|
5
> 𝑉(1,
4) = 4
|
Include
|
4
– 4 = 0
|
The table traces each comparison, inclusion decision, and resulting capacity. section 6.2.6








