Imagine you're packing a daypack for a hike. It can only hold so much weight before it's miserable to carry. On the table sits a water bottle, a camera, a sandwich, a paperback, a first-aid kit — each one weighs something, and each one is worth something to you. You can take an item or leave it, but you can't take half a camera. Which combination is worth the most without overloading the pack? That single question is the 0/1 knapsack problem.
To turn it into math, give each item a weight $w_i$ and a value $v_i$, and call the pack's limit $W$. The "0/1" just means every item is all-or-nothing. Here's the catch that makes knapsack famous: a greedy "grab the best bang-for-the-buck first" rule can fail. Suppose the pack holds 5 kg and you own a 3 kg item worth 4, a 4 kg item worth 5, and a 5 kg item worth 6. Greedy grabs the 3 kg item (best value-per-kg), then nothing else fits — total value 4. But the single 5 kg item is worth 6. Greedy loses by being short-sighted.
The fix: a table of best answers. Build $dp[i][w]$ = the most value you can get using only the first $i$ items with a weight budget of $w$. For each item you pick the better of two choices — skip it and keep $dp[i-1][w]$, or take it (when it fits) and get $dp[i-1][w-w_i]+v_i$:
$$dp[i][w]=\max\big(dp[i-1][w],\; dp[i-1][w-w_i]+v_i\big).$$
Fill the table row by row; the final answer waits at $dp[n][W]$.
This runs in $O(nW)$ time and space — quick when the budget $W$ is small. But notice $W$ is a number, not a count of items: adding one bit to $W$ can roughly double the work, which is exactly why knapsack is still NP-hard and the $O(nW)$ method is called "pseudo-polynomial." A neat trick collapses the memory to a single row of length $W$ if you sweep $w$ from high to low, which guarantees each item is counted at most once (left-to-right would let you reuse an item, solving a different problem).
Try this in the sim above. The panel here animates the item array and an operation counter rather than the DP grid, so use it to feel the scale: drag the n slider from 4 up to 16 and watch the Comparisons number climb. Load the Special preset to see how a few heavy-value items dominate the picture. Then press Next repeatedly to step through one operation at a time and watch how the work grows with the input size.
§3 — Algorithm Analysis & Derivation
Symbol
Meaning
n
Input size (vertices V, edges E, or array length)
T(n)
Time complexity function
W(n)
Worst-case complexity
A(n)
Average-case complexity
h
Height or depth of structure
k
Number of distinct values / items
Step 1 -- Optimal Substructure. For n items and capacity W: either item n is in the optimal solution or it is not. If not: solve for n-1 items with capacity W. If yes: solve for n-1 items with capacity W-weights[n], add values[n]. Optimal substructure holds: optimal solution built from optimal sub-solutions.
Step 2 -- Recurrence. dp[i][w] = maximum value using first i items with capacity w. dp[i][w] = dp[i-1][w] if item i doesn't fit (weights[i] > w). dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i]] + values[i]) otherwise.
Step 3 -- Time and Space O(nW). Two nested loops: O(nW). Table size: O(nW). This is PSEUDO-polynomial -- polynomial in n and W, but W can be exponential in the number of bits (W is an integer, not a count). True polynomial algorithm for 0/1 knapsack is unknown (NP-hard problem).
Step 4 -- Space Optimization to O(W). Only need previous row dp[i-1] to compute dp[i]. Use two 1D arrays (or one, traversed right-to-left). Right-to-left traversal ensures dp[i-1][w-weights[i]] is used (not the already-updated dp[i] value).
Step 5 -- Traceback. Start at dp[n][W]. If dp[n][W] != dp[n-1][W]: item n was taken, move to dp[n-1][W-weights[n]]. Else: item n not taken, move to dp[n-1][W]. Repeat for i=n-1,...,1.
Step 6 -- Variants. Unbounded knapsack: each item can be taken multiple times -- traverse capacity left-to-right in 1D DP. Fractional knapsack: greedy (sort by value/weight ratio). Multiple knapsacks: DP extended. Knapsack is NP-hard in general -- no polynomial algorithm known.
§4 — Frequently Asked Questions
What is the difference between 0/1 and fractional knapsack? concept+
0/1 Knapsack: each item taken whole or not at all. NP-hard, requires DP. Fractional: can take fractions of items. Greedy solution: sort by value/weight ratio, take greedily. O(n log n). 0/1 is harder because you cannot split items.
Why must the 1D DP traverse right-to-left? concept+
Right-to-left ensures that when computing dp[w], dp[w-weights[i]] still holds the i-1 row value (not the updated i row). Left-to-right would use the current row's already-updated values, implying the same item can be taken multiple times (= unbounded knapsack).
Is 0/1 Knapsack truly NP-hard? complex+
Yes, NP-hard (via reduction from Subset Sum). The O(nW) DP is PSEUDO-polynomial -- polynomial in n and W but exponential in the input size (W requires log W bits, so W = 2^(log W)). True polynomial algorithm would require O(poly(n, log W)).
Where is knapsack used in practice? applied+
Resource allocation in cloud computing (VMs into servers). Budget allocation (projects with costs and returns). Cryptography (knapsack cryptosystems, though broken). Compiler register allocation. Video streaming (fit max quality segments in bandwidth budget).
How to handle very large W values? nonobv+
If W is huge (e.g., 10^9) but n is small: use meet-in-the-middle -- split items into two halves, enumerate all 2^(n/2) subsets each, merge. O(2^(n/2) * n). Faster than O(nW) when W >> 2^(n/2). Also: FPTAS -- approximate within (1-epsilon) in O(n^2/epsilon).
What is the FPTAS for knapsack? deep+
Fully Polynomial-Time Approximation Scheme: scale down values by factor K = epsilon*max_v/n, round to integers, run DP with scaled values. Space O(n^2/epsilon), time O(n^2/epsilon). Gives (1-epsilon)-approximation. Only NP-hard problems with FPTAS are weakly NP-hard (like knapsack). Strongly NP-hard problems (like 3-SAT) have no FPTAS unless P=NP.
§5 — Common Misconceptions & Errors
Conceptual Misconceptions
✗ 0/1 Knapsack can be solved greedily.
✓ Greedy by value/weight ratio fails for 0/1 Knapsack. Classic counterexample: items (weight=3,val=4),(weight=4,val=5),(weight=5,val=6), W=5. Greedy takes item 1 (ratio 1.33) getting value 4. DP: item 2+item 1 doesn't fit, but item 3 gives 6 > 4.
✗ O(nW) DP is a polynomial-time algorithm.
✓ O(nW) is pseudo-polynomial. W is an input VALUE, not a count. Representing W takes log W bits. True polynomial would be O(n * poly(log W)).
✗ 1D DP traversal direction doesn't matter.
✓ For 0/1 Knapsack: must traverse RIGHT-TO-LEFT. Left-to-right gives unbounded knapsack (item reuse allowed).
Implementation Errors
✗ Forgetting the base case dp[0][w] = 0 for all w.
✓ No items means zero value regardless of capacity. dp[0][w] = 0. Also dp[i][0] = 0: zero capacity means no items can be taken.
✗ Initializing dp to -INF instead of 0 for 'can we fill exactly W' variant.
✓ For max-value: initialize to 0. For exact-fill variant (can we pack exactly W weight): initialize dp[i][w] = -INF for w>0, dp[i][0] = 0. Different initialization for different problem variants.
✗ Traversing the traceback forward instead of backward.
✓ Traceback starts at dp[n][W] and moves backward through rows n, n-1,...,1. Forward traceback gives wrong item selection.