Challenge: Reconstruct Items

The DP table gives you the maximum value, but which items did you take? You can reconstruct by backtracking. Start at $dp[n][W]$.

If $dp[i][w] \neq dp[i-1][w]$, you took item $i$. Move to $dp[i-1][w - weight[i]]$. If equal, you didn't take it. Move to $dp[i-1][w]$. Try this on the previous example. Start at $dp[3][5]=7$. Is $dp[2][5]=7$? Yes, so we didn't take item 3. Is $dp[1][5]=3$? No, $dp[2][5] \neq dp[1][5]$, so we took item 2.

Now at $dp[1][2]=3 \neq dp[0][2]=0$, so we took item 1. Items taken: 1 and 2. This backtracking works for all knapsack variants. The key is checking whether the value changed.