Chapter 57: DSA The 0/1 Knapsack Problem

The 0/1 Knapsack Problem is one of the most classic, most important, and most frequently asked problems in Data Structures & Algorithms — especially in interviews.

It belongs to a family of problems called knapsack problems, and the 0/1 version is the one almost everyone means when they say “knapsack problem”.

Let me explain it to you like we are sitting together, solving it step by step on paper — slowly, clearly, with real numbers, tables, intuition, and no rush.

1. Real-life story version (so you feel the problem)

Imagine you are a thief who has broken into a museum.

You have a backpack that can carry at most W = 10 kg of weight.

There are 5 very valuable items in front of you:

Rules:

• You can take at most one piece of each item (you cannot take 2 pieces of item 1)
• You cannot break any item — you either take the whole item or leave it
• Goal: maximize the total value you steal without exceeding 10 kg

This is exactly the 0/1 Knapsack Problem.

• 0/1 = you either take the item (1) or leave it (0)
• No fractions allowed (unlike Fractional Knapsack)

2. Formal definition (what interviewers expect)

Given:

• n items
• Each item i has:
  • weight wᵢ
  • value vᵢ
• Knapsack has maximum capacity W (weight limit)

Find a subset of items such that:

• Total weight ≤ W
• Total value is maximized

You cannot take fractional parts of items.

3. Why it’s hard – Brute force way (to feel the pain)

There are n items → each item can be either taken or not taken.

Total possible subsets = 2ⁿ

For n = 20 → 1 million possibilities For n = 40 → 1 trillion possibilities For n = 60 → impossible

So brute force is exponential time — only works for very small n (n ≤ 20–25).

4. The correct way: Dynamic Programming (most common solution)

We use dynamic programming to solve it efficiently.

We build a 2D table dp where:

dp[i][w] = maximum value we can achieve using first i items with maximum weight limit w

Size of table: (n+1) × (W+1)

Base case:

• dp[0][w] = 0 for all w → no items → value = 0
• dp[i][0] = 0 for all i → weight limit 0 → value = 0

Recurrence relation (the heart of the solution):

For each item i and each possible weight w:

We have two choices:

1. Do not take item i → dp[i][w] = dp[i-1][w]
2. Take item i (only if w ≥ wᵢ) → dp[i][w] = vᵢ + dp[i-1][w – wᵢ]

Take the maximum of these two choices:

dp[i][w] = max(     dp[i-1][w],     vᵢ + dp[i-1][w – wᵢ] (only if w ≥ wᵢ) )

5. Step-by-step example (very detailed table)

Items:

Knapsack capacity W = 10

We build table dp[6][11] (0 to 5 items, 0 to 10 weight)

Initialize:

All dp[0][w] = 0 All dp[i][0] = 0

Filling row by row (item 1 to 5)

After item 1 (weight 2, value 12)

w from 0 to 10:

• w < 2 → dp[1][w] = 0
• w ≥ 2 → max( dp[0][w], 12 + dp[0][w-2] ) = max(0, 12 + 0) = 12

Row 1: 0 0 12 12 12 12 12 12 12 12 12

After item 2 (weight 1, value 10)

For w = 0 → 0 w = 1 → max(0, 10 + dp[1][0]) = 10 w = 2 → max(12, 10 + dp[1][1]) = max(12, 10) = 12 w = 3 → max(12, 10 + dp[1][2]) = max(12, 22) = 22 and so on…

Row 2: 0 10 12 22 22 22 22 22 22 22 22

Continue this way until item 5.

Final dp[5][10] = 65 (maximum value)

One possible selection: items 1,2,4,5 → 2+1+3+5 = 10 kg, value = 12+10+25+30 = 65

6. Time & Space Complexity

Time Complexity: O(n × W) We fill a table of size (n+1) × (W+1), each cell takes O(1) time

Space Complexity: O(n × W) for the full table But we can optimize to O(W) using only 1D array (very common optimization)

7. Summary – What you should say in interviews

“The 0/1 Knapsack Problem asks us to maximize the total value of items we can put into a knapsack of capacity W, where each item can be taken at most once (0 or 1). It is a classic dynamic programming problem with time complexity O(n × W) and space complexity O(n × W) (optimizable to O(W)). We build a DP table where dp[i][w] represents the maximum value using the first i items with weight limit w. The recurrence is: dp[i][w] = max( dp[i-1][w], vᵢ + dp[i-1][w – wᵢ] ) if w ≥ wᵢ This problem appears very frequently in interviews because it tests understanding of dynamic programming, state definition, recurrence relation, and space optimization.”

8. Quick Cheat Sheet – 0/1 Knapsack

Do you want to continue deeper into 0/1 Knapsack?

Common next topics:

• Space-optimized version (1D DP) – very common in interviews
• How to reconstruct the actual items selected
• 0/1 Knapsack vs Unbounded Knapsack comparison
• Multiple constraints (two weights, profit maximization, etc.)
• Why greedy fails in 0/1 Knapsack (with counterexample)

Just tell me which one you want — I’ll explain it in the same detailed, calm, teacher style with clear tables and examples 😊