The 0/1 Knapsack Introduction

Imagine You’re Going on a Hiking Trip

You have a backpack that can hold only 6 kg. You want to pack items to make your trip as enjoyable as possible, but you can’t carry everything.

Here are your options:

Item	Weight	How much you want it
Game console	4 kg	10 points
Books	3 kg	7 points
Chocolates	2 kg	6 points
Headphones	1 kg	5 points

Your goal: pack items worth the most “enjoyment points” without going over 6 kg.

That’s the Knapsack Problem. Simple as that.

Why Is It Called “0/1”?

Because each item is either in or out. No halves. No cutting the game console in two.

0 = leave it behind
1 = pack it

Why Can’t You Just Grab the Most Valuable Things?

Let’s try. The game console scores 10 points — grab it first. That’s 4 kg used, 2 kg left. Now you can only fit the chocolates (2 kg, 6 points). Total: 16 points, 6 kg.

But wait — what if you skip the console and instead pack books + chocolates + headphones? That’s 3+2+1 = 6 kg, and 7+6+5 = 18 points. Better!

Greedy thinking — always grabbing the most valuable item — doesn’t always work. You need to consider every combination. That’s where Dynamic Programming comes in.

What Is Dynamic Programming, Really?

Think of it like this.

You’re doing a big jigsaw puzzle. Instead of starting from scratch every time you add a piece, you build on what you’ve already solved. Each new piece connects to previous work.

Dynamic Programming does the same thing with problems:

Solve small versions of the problem first. Use those answers to solve bigger versions. Never solve the same thing twice.

Solving It Step by Step — No Maths Required

Think of a grid. Rows are your items. Columns are bag sizes from 0 kg to 6 kg. Each cell answers one question:

“If I only had THESE items and THIS much bag space, what’s the best I can do?”

You fill it in row by row, left to right. For each item, you ask two questions:

1. Does this item even fit? If the item weighs more than the current column (bag size), you can’t take it. Copy the answer from the row above.

2. If it fits, is it worth taking? Compare two options:

Skip it → same answer as the row above
Take it → its value + best answer for the remaining space

Pick whichever is higher. Write it in the cell.

By the time you reach the bottom-right corner, you have your answer.

Walking Through Our Example

Let’s add items one by one.

Starting point: Empty bag = 0 points, regardless of size. ✓

Add Headphones (1 kg, 5 pts):

0 kg bag? Can’t fit. → 0 pts
1 kg bag? Fits! Take it. → 5 pts
2 kg bag? Still just 5 pts (only one headphone to take)
Same all the way to 6 kg → 5 pts

Add Chocolates (2 kg, 6 pts):

0–1 kg bag? Chocolates don’t fit. Copy from above → 0 or 5 pts
2 kg bag? Can take chocolates (6 pts) or headphones (5 pts). Take chocolates → 6 pts
3 kg bag? Chocolates (6) OR headphones (5) OR both (11)! → 11 pts
Carry this logic forward…

Keep adding items. Each row gets smarter by learning from all the rows before it.

Final answer (bottom-right cell): 18 points — books + chocolates + headphones.

The Code example

def knapsack(weights, values, capacity):

    # Make a grid: rows = items, columns = bag sizes
    dp = [[0] * (capacity + 1) for _ in range(len(weights) + 1)]

    for i in range(1, len(weights) + 1):
        for bag_size in range(capacity + 1):

            # This item is too heavy — skip it
            if weights[i-1] > bag_size:
                dp[i][bag_size] = dp[i-1][bag_size]

            # Item fits — choose the better option
            else:
                skip_it = dp[i-1][bag_size]
                take_it = dp[i-1][bag_size - weights[i-1]] + values[i-1]
                dp[i][bag_size] = max(skip_it, take_it)

    return dp[len(weights)][capacity]

Read the code like plain English:

Build a grid of answers
For each item, for each possible bag size
If it’s too heavy → skip (copy from above)
If it fits → compare skipping vs taking, keep the best

The “Aha!” Moment

Here’s the beautiful idea at the heart of this:

Every big decision is just a collection of small decisions, each one recorded and reused.

When you’re deciding whether to pack the game console with a 6 kg bag, you don’t recalculate everything from scratch. You already know the best answer for a 2 kg bag (from filling in that column earlier). You look it up.

That’s Dynamic Programming. Remember past answers. Build forward. Never repeat work.

Quick Recap

Question	Answer
What’s the problem?	Pack a bag to maximize value without exceeding weight
Why not try everything?	Too many combinations — grows exponentially
Why not grab most valuable first?	Greedy fails — misses better combinations
What does DP do?	Solves small cases first, builds up to the full answer
How fast is it?	O(n × W) — much better than trying all combinations

What to Learn Next

Once this clicks, you’re ready for:

Unbounded Knapsack — what if you could pack the same item multiple times?
Coin Change Problem — same idea, different story
Longest Common Subsequence — DP applied to strings
Matrix Chain Multiplication — DP for ordering operations

The pattern is always the same: break it down, solve small, build up, reuse answers. Master that, and you’ve unlocked one of the most powerful tools in programming.

Did this post help you better understand the concept? Let me know your thoughts in the comments below! Don’t forget to follow us on Instagram @coderz.py for more DP tips and solutions to ace your coding interviews.