If you’re struggling to really “get” the Knapsack problem or Subset Sum DP tables, you’re not alone. I used to look at those cryptic tables and think, “What are these numbers even doing here?!” But once you know why the table changes the way it does, it all starts to click.

Let me walk you through a super-friendly and visual explanation using an actual DP table from a Subset Sum problem. We’ll break down the recurrence, uncover how to detect item weights from a filled-in table, and understand what those weird value jumps really mean.

The Setup: Subset Sum with 3 Items

You’re given a filled DP table like this (rows = items, columns = knapsack capacities):

   w:     0  1  2  3  4  5  6  7  8  9
-------------------------------------
 i=3 |    0  0  2  3  3  5  5  7  8  8
 i=2 |    0  0  2  2  2  5  5  7  7  7
 i=1 |    0  0  0  0  0  5  5  5  5  5
 i=0 |    0  0  0  0  0  0  0  0  0  0

We don’t know the item weights yet. All we know is:

• There are 3 items (i = 1, 2, 3)
• Knapsack capacity goes from 0 to 9

In this problem, we want to answer: What are the item weights? And more importantly, how does this table even work?

What Does the Table Represent?

This is a classic Subset Sum DP table.
Each cell OPT(i, w) means:

What’s the maximum total weight we can pack using the first i items into a knapsack of capacity w?

The recurrence that fills this table is:

OPT(i, w) = max(
    OPT(i-1, w),                    # Don’t take item i
    OPT(i-1, w - weight[i]) + weight[i]   # Take item i, if it fits
)

We build this row-by-row, seeing whether the new item improves the result.

Step 1: How Do We Find the Item Weights?

We look at when values first increase in a new row.

i = 1:

We compare row 1 to row 0:

• Everything is 0 until column w = 5, where it jumps to 5
• That means the first item has weight 5

i = 2:

Compare row 2 to row 1:

• First jump is at w = 2, goes from 0 to 2
• So the second item is weight 2

i = 3:

Compare row 3 to row 2:

• First jump is at w = 3, goes from 2 to 3
• Third item must be weight 3

Final weights: 5, 2, 3

Step 2: What Do the Later Changes Mean?

Okay, so we found the weights. But why do later values like 7, 8, etc. show up? That’s where the magic of combos comes in.

Each later increase is caused by combining the new item with previous subsets.

For example:

• OPT(3, 8) = 8
• That comes from: OPT(2, 5) = 5 + weight of item 3 = 3

So the 8 means: we took item 3 (w=3), and a previous combo that totaled 5 (which was just item 1).

Visual Chart: Where Each Value Comes From

Let’s visualize row i = 3 to see exactly how each value formed:

Capacity (w):   0  1  2  3  4  5  6  7  8  9
----------------------------------------------------
From i=2:       0  0  2  2  2  5  5  7  7  7

Added w=3?      N  N  N  ✔  ✔  N  N  N  ✔  N
New value:      -  -  -   3   3  -  -  -   8  -
Explanation:
  w=3: used item 3 (3) alone
  w=4: used item 3 (3) + OPT(2,1)=0
  w=8: used item 3 (3) + OPT(2,5)=5

You can see how item 3 “builds on top” of what we already had.

Essentially:

• The DP table tracks the best weight you can get at each step
• The initial jumps tell you the individual item weights
• The later increases are combos: “this item + something from before”
• The recurrence is really asking: “Is adding this item better than not adding it?”

The Subset Sum (and Knapsack) DP tables aren’t as mysterious once you know how to read them:

• Use initial jumps to decode weights
• Use combos to explain value growth
• Trust the recurrence: it’s just comparing include vs don’t-include

I hope this helped you see the DP table not just as a bunch of numbers, but as a conversation: “Should I include this item? What happens if I do?”

So far, we’ve explored the Subset Sum problem where all we cared about was total weight. But the full 0/1 Knapsack problem takes things one step further by giving each item not only a weight but also a value.

In Subset Sum:

• Each item has only a weight.
• The goal is to pack the heaviest possible total weight without exceeding the bag’s capacity.

In 0/1 Knapsack:

• Each item has both a weight and a value.
• The goal is to pack items such that the total value is maximized, without the total weight exceeding capacity.

This changes the entire game because you can’t just go for what fits — you have to make tradeoffs between value and weight.

Example

Suppose your knapsack has capacity 5, and you’re given:

Item	Weight	Value
A	2	100
B	3	60
C	4	70

In Subset Sum, you’d look for combinations that get you as close as possible to 5 weight.

In 0/1 Knapsack, you evaluate the value per weight and choose A and B (2+3=5 weight, 100+60=160 value), because that gives the best bang for your buck.

New Recurrence

Now, instead of tracking total weight, the DP table tracks total value:

OPT(i, w) = max(
    OPT(i-1, w),                      # Don't take item i
    OPT(i-1, w - wᵢ) + vᵢ           # Take item i, if it fits
)

This subtle change opens the door to strategic optimization, not just packing, but choosing what’s worth it.

I hope all of this helps.