Filling the Table
The Filled Table
Once every cell is filled, the final state contains the optimal value. The table is not an approximation or a solver trace; it is the recurrence written out. This lesson reads the whole grid as the completed computation and emphasizes why the bottom-right state is the original knapsack question.
Filled table
The full table has 5 rows and 8 columns. Why: every item prefix is paired with every capacity, so the table covers the exact state space of the recurrence. A row says which items are allowed; a column says how much capacity is available. Together they name a smaller knapsack problem whose answer can be reused.
Answer location
The bottom-right cell is 9. Why: it uses all items and the full capacity, which is exactly the original instance rather than a restricted subproblem. The rest of the table exists so this final state can be read without reconsidering every subset. That is the payoff of storing subproblem answers.
Diagram note
Every entry in the table is recomputed by the knapsack recurrence. The completed grid is a proof object as well as a calculation: each cell has already compared the only two zero-one possibilities for its current item. The table is exact for this pinned instance, while its pseudo-polynomial size honestly depends on the capacity magnitude. Pixel positions are rounded for layout; every number shown is exact.