liveBook · Manning

Backtracking

As explained in Timeless Algorithms, The Foundational Ideas

Backtracking is a technique that reconstructs a solution by tracing stored decisions backward from a final state.

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

How Timeless Algorithms, The Foundational Ideas covers it

How deep it goes
Defines state comparisons, inclusion and exclusion decisions, capacity updates, and the stopping condition; notes alternative optima on ties.
Examples
Traces a capacity-seven knapsack with four items to the optimal set of Items 2, 3, and 4.
What it assumes
Assumes a completed dynamic-programming table and its final optimal state are available.
What you can do after
Understand which decisions produced an optimal value by tracing a completed table backward.
How it connects
Connects dynamic programming, tabulation, and the 0/1 knapsack problem.

Also explained in

Compare how 9 books explain backtracking →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Timeless Algorithms, The Foundational Ideas. The section links point to the parts of the book it draws on.