The 0-1 Knapsack - Knapsack and the DP Table

Knapsack starts with items that have integer weights and values, then asks for a subset that fits a fixed capacity. Greedy instincts are useful for intuition but not reliable here, because a locally attractive item can crowd out a better combination. Dynamic programming matters because it preserves the exact zero-one choices while avoiding repeated subset work.

highlighted = computed this step

Items and capacity

There are 4 items and capacity 7. Why: each item consumes capacity and contributes value, so the problem is not just to choose the largest value item. A tempting greedy rule can spend capacity too early and block a better combination. The capacity is the shared budget that makes the choices interact.

W=7

Subset search

Brute force checks 16 subsets here. Why: each item is either left out or put in, so the search tree doubles with each new item. That growth is the reason the lesson does not inspect subsets one by one. Dynamic programming keeps the same exact choices but stores reusable partial answers.

2^{4}=16

Diagram note

The instance data are integers and the capacity is exact; no DP values have been filled yet. This diagram is the input boundary for the book: it says what may be chosen and how much weight can fit, not which subset is best. The DP table that follows is exact for this zero-one integer knapsack instance and grows with the capacity magnitude, so the method is pseudo-polynomial rather than a universal small-table shortcut. Pixel positions are rounded for layout; every number shown is exact.

\text{integer data enter the DP table}