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:
| Item | Weight (kg) | Value (₹) |
|---|---|---|
| 1 | 2 | 12 |
| 2 | 1 | 10 |
| 3 | 6 | 40 |
| 4 | 3 | 25 |
| 5 | 5 | 30 |
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:
- Do not take item i → dp[i][w] = dp[i-1][w]
- 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:
| Item | Weight | Value |
|---|---|---|
| 1 | 2 | 12 |
| 2 | 1 | 10 |
| 3 | 6 | 40 |
| 4 | 3 | 25 |
| 5 | 5 | 30 |
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
| Question | Answer |
|---|---|
| Time complexity | O(n × W) |
| Space complexity (naive) | O(n × W) |
| Space complexity (optimized) | O(W) |
| Stable? | — (not a sorting problem) |
| When to use | When we have weight constraint + 0/1 choice per item |
| Common variations | Unbounded Knapsack, Fractional Knapsack, 0/1 Knapsack with multiple constraints |
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 😊
