Skip to interview prep
Apexed

369. How do 0/1 knapsack and unbounded knapsack differ in their DP?

MediumDynamic programming

Technical
Show model answer

Let best[w] be the maximum value with capacity w. For 0/1 knapsack each item is used at most once, so for each item loop w from W down to the item's weight: `best[w] = max(best[w], best[w − wt] + val)`. Iterating downward guarantees best[w − wt] still refers to the state before this item was considered. For unbounded knapsack, loop w upward instead, so the same item can be added again.

Both run in O(nW) time and O(W) space (the full 2D table, O(nW) space, is needed if you want to reconstruct the chosen items). This is pseudo-polynomial: W is a number, so the input only needs O(log W) bits to describe it. Knapsack is NP-complete; when W is huge but values are small, DP over value instead of weight can work better.

What interviewers listen for

  • 0/1: iterate capacity downward
  • Unbounded: iterate capacity upward
  • Pseudo-polynomial O(nW)
How do 0/1 knapsack and unbounded knapsack differ in their DP — Data structures & algorithms interview question — Apexed