In Chapter 1, we built the DP mindset: recognise choices, find repeated subproblems, store answers instead of recomputing them. We didn't write a single DP table. We didn't touch a 2D array. We just learned how to think.
Chapter 2 is where that thinking meets its first real problem.
0/1 Knapsack is not just one problem. It's a pattern. Once you understand it deeply, a whole family of problems: Subset Sum, Equal Partition, Count of Subsets, Target Sum, Minimum Subset Difference — start looking like variations of the same idea. That's why we start here.
What Is the 0/1 Knapsack Problem?
You have a bag with a weight capacity W. You have n items, each with a weight and a value. You want to fill the bag to maximise total value without exceeding the capacity.
Weight: [1, 3, 4, 5]
Value: [1, 4, 5, 7]
Capacity W = 7
The critical constraint: each item can either be taken once or not taken at all. No fractions. No repeats. That's the 0/1 part.
0 → skip the item
1 → take the item
This is an optimisation problem (you want maximum value) where you have choices at every step (take or skip). Both conditions together are the first signal that DP is the right approach.
Step 1: Identify the Choices
Before writing any code, draw the choices.
At each item, you face exactly two options:
Current Item
/ \
TAKE SKIP
If you TAKE it:
- You gain
val[n-1]value - Your remaining capacity becomes
W - wt[n-1] - You move to the next item:
n-1
If you SKIP it:
- You gain nothing
- Capacity stays
W - You still move to the next item:
n-1
There's one constraint on the TAKE branch: you can only take the item if it actually fits. If wt[n-1] > W, the TAKE option disappears entirely and you can only skip.
Step 2: Identify the Base Case
Ask: what is the smallest valid input, and what does it return?
Two situations stop the recursion:
-
n == 0: no items left to consider -
W == 0: no capacity remaining
In both cases, the maximum value you can achieve is zero.
if n == 0 or W == 0:
return 0
Base case identified. Now write the recursion.
Step 3: Write the Recursive Solution
The base case and choice diagram translate directly into code. This is the whole point of drawing the choice diagram first.
def knapsack(wt, val, W, n):
# Base Case — no items or no capacity
if n == 0 or W == 0:
return 0
# Choice Diagram — item fits, so two choices exist
if wt[n-1] <= W:
return max(
val[n-1] + knapsack(wt, val, W - wt[n-1], n-1), # TAKE
knapsack(wt, val, W, n-1) # SKIP
)
# Item doesn't fit — only one choice
else:
return knapsack(wt, val, W, n-1) # forced SKIP
The code is not something you memorised. It came directly from the choice diagram. That's the connection to hold onto.
Step 4: Find the Repeated States
The recursive solution works correctly but does redundant work. The same subproblem can appear multiple times across different branches of the recursion tree.
The state of any call is completely defined by two values: n and W. Everything else (the arrays wt and val) never changes. So if Knapsack(3, 5) appears twice in the recursion tree, both calls would return the exact same answer.
This repeated work is exactly what DP eliminates. Instead of recomputing Knapsack(2, 2) twice, compute it once, store the answer, and return it when the state appears again.
Step 5: Add Memoization (Top-Down DP)
Since the state is defined by (n, W), we need a matrix of size (n+1) × (W+1) to store every possible state.
Why n+1 and W+1? Because n ranges from 0 to n and W ranges from 0 to W. We need a slot for every value including zero.
T = [[-1] * (W + 1) for _ in range(n + 1)]
The -1 means "not yet computed." Once a state is computed, its answer replaces the -1.
The recursive code changes in exactly one place: before computing anything, check if the answer is already stored.
class Solution:
def knapsack(self, W, val, wt):
n = len(wt)
T = [[-1] * (W + 1) for _ in range(n + 1)]
def solve(n, W):
# Base Case
if n == 0 or W == 0:
return 0
# Already computed? Return stored answer
if T[n][W] != -1:
return T[n][W]
# Choice Diagram
if wt[n-1] <= W:
T[n][W] = max(
val[n-1] + solve(n-1, W - wt[n-1]), # TAKE
solve(n-1, W) # SKIP
)
else:
T[n][W] = solve(n-1, W) # forced SKIP
return T[n][W]
return solve(n, W)
The diff from pure recursion to memoization is genuinely small: create the table, check before computing, store after computing. The structure of the solution doesn't change at all.
Step 6: Convert to Bottom-Up Tabulation
Memoization starts from the top and recurses down. Tabulation starts from the bottom and builds up. Both arrive at the same answer.
The connection between the two is direct:
- The base cases from recursion become the initial values of the table
- The recursive calls become table lookups
- The
nandWparameters become loop indicesiandj
Since our base case was n == 0 or W == 0 → return 0, we initialise the entire table with zeros. Both base cases are handled in one line.
T = [[0] * (W + 1) for _ in range(n + 1)]
Then fill the table row by row, left to right, using the same transition from the recursive solution:
class Solution:
def knapsack(self, W, val, wt):
n = len(wt)
# Initialise with zeros — base cases already handled
T = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, W + 1):
if wt[i-1] <= j:
T[i][j] = max(
val[i-1] + T[i-1][j - wt[i-1]], # TAKE
T[i-1][j] # SKIP
)
else:
T[i][j] = T[i-1][j] # forced SKIP
return T[n][W]
The Complete Flow in One Picture
What the Table Cell Actually Means
This is the part worth pausing on because it makes every future DP table easier to read.
T[i][j] means: the maximum value achievable using the first i items with a bag capacity of exactly j.
So T[3][5] answers: "what's the best I can do with items 1, 2, and 3, if my bag holds 5 kg?" The final answer T[n][W] answers the original question: best value using all n items with full capacity W.
Every DP table you'll ever see has a similar interpretation. The indices represent the "state" of the problem at that point. Understanding what the indices mean is more important than knowing how to fill the table mechanically.
What This Pattern Unlocks
The 0/1 Knapsack pattern is not just one problem. It's a template.
0/1 Knapsack
↓
Subset Sum — can we reach exactly a target weight?
↓
Equal Sum Partition — can we split into two equal subsets?
↓
Count of Subsets — how many ways to reach a target sum?
↓
Min Subset Diff — minimise the difference between two subsets
↓
Target Sum — assign + and − to reach a target
↓
Count Subsets with Given Difference
Every problem in this list uses the same foundation: items, binary choices (take or skip), a state defined by the remaining items and remaining capacity, and a transition that combines answers from smaller states.
The surface details change. The underlying structure doesn't.
What You Now Understand
The 0/1 Knapsack solution was never about memorising a 2D array. It came from a choice diagram (take or skip), a base case (no items or no capacity), and a transition that said "take the maximum of both options."
Memoization stored the answers to avoid repeating work. Tabulation filled those same answers bottom-up without recursion. Both used the exact same transition.
Chapter 3 applies this pattern to Subset Sum, where the same take-or-skip logic solves a completely different-looking problem. If the pattern clicks here, Subset Sum will feel like a variation rather than something new.
Top comments (0)