0/1 Knapsack Problem

Question 1

What does dp[i][w] represent?

Accepted Answer

Max value with first i, capacity w — Each cell stores the maximum value achievable considering a subset of items 1..i within the specific capacity limit w.

Question 2

In the 0/1 knapsack problem, each item can be…

Accepted Answer

Taken at most once per solution — 0/1 knapsack allows each item to be either fully taken or left out — no fractions and no repeats.

Question 3

The DP recurrence for 0/1 knapsack at item i, capacity w is dp[i][w] =…

Accepted Answer

max(dp[i-1][w], dp[i-1][w−wt]+val) — You choose the better of excluding item i (dp[i-1][w]) or including it (value[i] plus the best for the remaining capacity).

Question 4

The time complexity of the standard 0/1 knapsack DP is…

Accepted Answer

O(n·W) where n = items, W = capacity — The table has n items × W capacities, each filled in O(1): O(nW). This is pseudo-polynomial, not truly polynomial.

Question 5

Why is O(nW) called PSEUDO-polynomial rather than polynomial?

Accepted Answer

W's value is exponential in its log-W bit-length — Capacity W takes only log W bits to write, so O(nW) is exponential in the bit-length of W — hence 'pseudo-polynomial', and 0/1 knapsack is NP-hard.

Question 6

The 0/1 knapsack DP can be space-optimized to…

Accepted Answer

O(W) using a 1D array updated in reverse — A rolling 1D array updated from high capacity down to low reuses only the previous row, cutting space to O(W) while preserving the 0/1 'each item once' rule.

Question 7

Why must the 1D 0/1-knapsack array be iterated from HIGH capacity to LOW?

Accepted Answer

To avoid reusing the same item twice — Updating low→high would let dp[w − weight] already include item i, double-counting it; reverse iteration ensures each item is considered once.

Question 8

The UNBOUNDED knapsack (unlimited copies of each item) differs by…

Accepted Answer

Iterating capacity from low to high — Forward iteration lets dp[w − weight] include the current item already, modeling taking it multiple times — the unbounded variant.

Question 9

The FRACTIONAL knapsack (items divisible) is solved optimally by…

Accepted Answer

A greedy sort by value-to-weight ratio — Unlike 0/1, fractional knapsack has the greedy-choice property: sorting by value-density and filling greedily is optimal in O(n log n).

Question 10

Why can't the greedy value/weight approach solve 0/1 knapsack optimally?

Accepted Answer

A high-ratio item can block a better combo — With whole items, locally best ratios don't guarantee a global optimum (you can't take a fraction to fill the gap), so DP is required for 0/1.

	0	1	2	3	4	5	6	7
Base	0	0	0	0	0	0	0	0
I1(w:1,v:1)	0	0 1,1	0	0	0	0	0	0
I2(w:3,v:4)	0	0	0	0	0	0	0	0
I3(w:4,v:5)	0	0	0	0	0	0	0	0
I4(w:5,v:7)	0	0	0	0	0	0	0	0

0/1 Knapsack Problem

Fill the knapsack table

Test your knowledge

What does dp[i][w] represent?

The short version

In more depth

The Choice Diagram

When to reach for this

Interview Questions

References & Further Reading

Love this visualization?