Items: i1 weighs 1 and is worth 1, i2 weighs 3 and is worth 4, i3 weighs 4 and is worth 5, i4 weighs 5 and is worth 7. Capacity 7. Cell (i, w) is the best value from the first i items within weight w. Row 0 has no items, so it is all zeros. 0/1: each item is taken at most once.
Building the 0/1 knapsack table for 4 items and capacity 7.
Item 1 (weight 1, value 1) at capacity 0. It does not fit, so only skipping is possible: copy the cell above, 0.
Item 1 at capacity 0: too heavy, so 0 from above.
Item 1 (weight 1, value 1) at capacity 1. Skip: 0 from above. Take: 1 + 0 from the previous row at capacity 0 = 1. Best: 1, take.
Item 1 at capacity 1: best of skip 0 and take 1 is 1.
Item 1 (weight 1, value 1) at capacity 2. Skip: 0 from above. Take: 1 + 0 from the previous row at capacity 1 = 1. Best: 1, take.
Item 1 at capacity 2: best of skip 0 and take 1 is 1.
Item 1 (weight 1, value 1) at capacity 3. Skip: 0 from above. Take: 1 + 0 from the previous row at capacity 2 = 1. Best: 1, take.
Item 1 at capacity 3: best of skip 0 and take 1 is 1.
Item 1 (weight 1, value 1) at capacity 4. Skip: 0 from above. Take: 1 + 0 from the previous row at capacity 3 = 1. Best: 1, take.
Item 1 at capacity 4: best of skip 0 and take 1 is 1.
Item 1 (weight 1, value 1) at capacity 5. Skip: 0 from above. Take: 1 + 0 from the previous row at capacity 4 = 1. Best: 1, take.
Item 1 at capacity 5: best of skip 0 and take 1 is 1.
Item 1 (weight 1, value 1) at capacity 6. Skip: 0 from above. Take: 1 + 0 from the previous row at capacity 5 = 1. Best: 1, take.
Item 1 at capacity 6: best of skip 0 and take 1 is 1.
Item 1 (weight 1, value 1) at capacity 7. Skip: 0 from above. Take: 1 + 0 from the previous row at capacity 6 = 1. Best: 1, take.
Item 1 at capacity 7: best of skip 0 and take 1 is 1.
Item 2 (weight 3, value 4) at capacity 0. It does not fit, so only skipping is possible: copy the cell above, 0.
Item 2 at capacity 0: too heavy, so 0 from above.
Item 2 (weight 3, value 4) at capacity 1. It does not fit, so only skipping is possible: copy the cell above, 1.
Item 2 at capacity 1: too heavy, so 1 from above.
Item 2 (weight 3, value 4) at capacity 2. It does not fit, so only skipping is possible: copy the cell above, 1.
Item 2 at capacity 2: too heavy, so 1 from above.
Item 2 (weight 3, value 4) at capacity 3. Skip: 1 from above. Take: 4 + 0 from the previous row at capacity 0 = 4. Best: 4, take.
Item 2 at capacity 3: best of skip 1 and take 4 is 4.
Item 2 (weight 3, value 4) at capacity 4. Skip: 1 from above. Take: 4 + 1 from the previous row at capacity 1 = 5. Best: 5, take.
Item 2 at capacity 4: best of skip 1 and take 5 is 5.
Item 2 (weight 3, value 4) at capacity 5. Skip: 1 from above. Take: 4 + 1 from the previous row at capacity 2 = 5. Best: 5, take.
Item 2 at capacity 5: best of skip 1 and take 5 is 5.
Item 2 (weight 3, value 4) at capacity 6. Skip: 1 from above. Take: 4 + 1 from the previous row at capacity 3 = 5. Best: 5, take.
Item 2 at capacity 6: best of skip 1 and take 5 is 5.
Item 2 (weight 3, value 4) at capacity 7. Skip: 1 from above. Take: 4 + 1 from the previous row at capacity 4 = 5. Best: 5, take.
Item 2 at capacity 7: best of skip 1 and take 5 is 5.
Item 3 (weight 4, value 5) at capacity 0. It does not fit, so only skipping is possible: copy the cell above, 0.
Item 3 at capacity 0: too heavy, so 0 from above.
Item 3 (weight 4, value 5) at capacity 1. It does not fit, so only skipping is possible: copy the cell above, 1.
Item 3 at capacity 1: too heavy, so 1 from above.
Item 3 (weight 4, value 5) at capacity 2. It does not fit, so only skipping is possible: copy the cell above, 1.
Item 3 at capacity 2: too heavy, so 1 from above.
Item 3 (weight 4, value 5) at capacity 3. It does not fit, so only skipping is possible: copy the cell above, 4.
Item 3 at capacity 3: too heavy, so 4 from above.
Item 3 (weight 4, value 5) at capacity 4. Skip: 5 from above. Take: 5 + 0 from the previous row at capacity 0 = 5. Best: 5, skip.
Item 3 at capacity 4: best of skip 5 and take 5 is 5.
Item 3 (weight 4, value 5) at capacity 5. Skip: 5 from above. Take: 5 + 1 from the previous row at capacity 1 = 6. Best: 6, take.
Item 3 at capacity 5: best of skip 5 and take 6 is 6.
Item 3 (weight 4, value 5) at capacity 6. Skip: 5 from above. Take: 5 + 1 from the previous row at capacity 2 = 6. Best: 6, take.
Item 3 at capacity 6: best of skip 5 and take 6 is 6.
Item 3 (weight 4, value 5) at capacity 7. Skip: 5 from above. Take: 5 + 4 from the previous row at capacity 3 = 9. Best: 9, take.
Item 3 at capacity 7: best of skip 5 and take 9 is 9.
Item 4 (weight 5, value 7) at capacity 0. It does not fit, so only skipping is possible: copy the cell above, 0.
Item 4 at capacity 0: too heavy, so 0 from above.
Item 4 (weight 5, value 7) at capacity 1. It does not fit, so only skipping is possible: copy the cell above, 1.
Item 4 at capacity 1: too heavy, so 1 from above.
Item 4 (weight 5, value 7) at capacity 2. It does not fit, so only skipping is possible: copy the cell above, 1.
Item 4 at capacity 2: too heavy, so 1 from above.
Item 4 (weight 5, value 7) at capacity 3. It does not fit, so only skipping is possible: copy the cell above, 4.
Item 4 at capacity 3: too heavy, so 4 from above.
Item 4 (weight 5, value 7) at capacity 4. It does not fit, so only skipping is possible: copy the cell above, 5.
Item 4 at capacity 4: too heavy, so 5 from above.
Item 4 (weight 5, value 7) at capacity 5. Skip: 6 from above. Take: 7 + 0 from the previous row at capacity 0 = 7. Best: 7, take.
Item 4 at capacity 5: best of skip 6 and take 7 is 7.
Item 4 (weight 5, value 7) at capacity 6. Skip: 6 from above. Take: 7 + 1 from the previous row at capacity 1 = 8. Best: 8, take.
Item 4 at capacity 6: best of skip 6 and take 8 is 8.
Item 4 (weight 5, value 7) at capacity 7. Skip: 9 from above. Take: 7 + 1 from the previous row at capacity 2 = 8. Best: 9, skip.
Item 4 at capacity 7: best of skip 9 and take 8 is 9.
Best value 9 with items i2, i3. 32 cells, each one comparison: O(items x capacity), which is fast when the capacity is small even though the subsets number 2 to the 4.
The best value is 9.