The Problem
The DP Idea
The DP table records smaller knapsack questions before using them in larger ones. Each row adds one more item, and each column fixes a capacity. The central interpretation is that a cell is not a guess or an approximation; it is the exact best value for a restricted subproblem whose answer can be reused safely.
State definition
The state dp at i,w means best value using the first i items with capacity w. Why: the table turns one large subset question into many prefix-and-capacity questions. The prefix limit matters because later rows are not allowed to reach backward and reuse an item twice. The capacity limit matters because each row must still respect the same bag constraint.
Take or leave
For item i, the recurrence compares leaving the item with taking it if it fits. Why: every feasible subset either contains the current item or does not, and those two cases exhaust the zero-one choice. Leaving the item keeps the previous row at the same capacity. Taking it moves to a smaller remaining capacity before adding the item's value.
First item
The first item has weight 1 and value 1, so every positive capacity can earn value 1. Why: once the item fits, there is no competing earlier item to compare against. This row is small, but it shows the meaning of a DP cell: the best value achievable under the row's item prefix and the column's capacity.
Diagram note
The displayed rows are copied from the recomputed DP table, not authored separately. They are the base of the later recurrence: every later cell will look only to already-computed prefix answers. The table is exact for this pinned zero-one integer instance, and its size grows with item count times capacity magnitude. Pixel positions are rounded for layout; every number shown is exact.