0/1 Knapsack DP in Java — Implementation, Optimization, vs Fractional (Greedy)

0/1 Knapsack

• n items with weights and values, capacity W
• Take each item whole or skip — no fractions
• Maximize total value within capacity
• NP-hard in general but DP-solvable in pseudo-polynomial time

DP recurrence

• State: dp[i][w] = max value using first i items with capacity w
• Transition: skip or take

  • Skip: dp[i-1][w]
  • Take (if fits): dp[i-1][w - weight[i]] + value[i]
  • Pick the bigger
• Base case: dp[0][w] = 0 (no items)
• Answer: dp[n][W]

2D DP — O(n·W) time, O(n·W) space

for (int i = 1; i <= n; i++) {
    for (int w = 0; w <= W; w++) {
        dp[i][w] = dp[i-1][w];
        if (weights[i-1] <= w)
            dp[i][w] = max(dp[i][w], dp[i-1][w - weights[i-1]] + values[i-1]);
    }
}

1D rolling array — O(W) space

• Only previous row matters
• dp[w] = max(dp[w], dp[w - weight[i]] + value[i])
• Critical: iterate w DESCENDING

Why descending?

• Ascending lets us 'take item i twice' (since dp[w - weight[i]] is updated within same iteration)
• That's the unbounded knapsack — wrong for 0/1
• Descending ensures dp[w - weight[i]] is from the previous row

Memorize the rule

• 0/1 → descending
• Unbounded → ascending

Reconstructing chosen items

• Need full 2D table
• Walk backward: if dp[i][w] != dp[i-1][w], item i was taken
• O(n) trace-back
• 1D version loses this ability

Memoization (top-down)

• Recursive solve(i, w) with cache
• Same O(n·W) complexity
• Useful when sparse states
• Watch stack depth

Pseudo-polynomial

• O(n·W) is polynomial in W's value but exponential in W's bit-length
• Therefore NP-hard, not in P
• W = 10^9 → 1B operations — infeasible

Fractional Knapsack — different problem

• Items can be taken in fractions (0.6 of item 3 OK)
• Greedy works: sort by value/weight ratio descending
• Take whole until can't fit, then fraction of next
• Time: O(n log n)
• Space: O(1) extra

Why greedy works for fractional

• Any leftover capacity can be filled with a fraction
• Exchange argument: if not following ratio order, swap improves
• Fully utilizes capacity

Why greedy fails on 0/1

• Counter-example: items (10,60), (20,100), (30,120), W=50

  • Greedy by ratio: take first two → value 160, leftover 20 unused
  • Optimal: take last two → value 220
• Integer constraint can leave capacity unused, breaking the argument

Variants

Unbounded knapsack

• Unlimited copies
• 1D DP with ascending w
• Coin change variants

Bounded knapsack

• k copies per item
• Decompose into 0/1 with binary representation (1,2,4,...,remainder copies)
• Reduces to O(n·log(k)·W)

Multi-dimensional knapsack

• Multiple constraints (weight + volume)
• Extra state dimensions: O(n·W·V)

Subset sum

• Special case: value = weight
• 'Can we hit exactly target sum?'

Partition into equal sum

• Subset sum with target = totalSum / 2

Meet-in-the-middle

• For small n (≤ 40) with huge W
• Split items into two halves, enumerate 2^(n/2) subsets each
• Sort one, binary-search for matches
• O(2^(n/2) · n)

Approximation algorithms

• FPTAS: (1-ε)-optimal in O(n^3 / ε)
• Scale values to integers, run DP on scaled
• Useful when W is huge AND exact answer not required

Branch-and-bound

• Exact solution for huge W
• Use fractional knapsack as upper bound to prune

Decision matrix

Use 0/1 DP

• W ≤ ~10^6 (so n·W ≤ 10^9 ish)
• Discrete items
• Need exact optimal

Use 1D rolling

• Same as above + don't need item reconstruction

Use 2D

• Need to know which items were chosen

Use meet-in-the-middle

• n ≤ 40, W huge

Use FPTAS

• Both n and W huge, approximation OK

Use fractional greedy

• Items truly splittable (cargo, budget allocation)

Common pitfalls

1. Ascending w in 1D version

• Becomes unbounded — wrong answer
• Always remember: 0/1 → descending

2. Confusing 0/1 with fractional

• Greedy on 0/1 gives suboptimal
• Read problem carefully

3. Off-by-one in dimensions

• Use dp[n+1][W+1] for ease (index from 1)
• Or dp[n][W+1] (index from 0) — watch base case

4. Integer overflow

• If values are large and many items, totalValue can exceed Integer.MAX_VALUE
• Use long

5. Memory limit

• O(n·W) can be too much; use 1D rolling

6. Stack overflow in memoization

• For deep recursion (n+W large)
• Use tabulation

Recommendation: For interviews, lead with the 2D DP — it directly mirrors the recurrence and is easy to explain (dp[i][w] = best value using first i items with capacity w; transition = max of skip or take). Then optimize to 1D rolling array with descending iteration for capacity — the descending order is critical and is itself an interview question (ascending would solve unbounded knapsack instead). Be ready to reconstruct chosen items by walking backward through the 2D table; this requires keeping the full table, so you can't combine reconstruction with the 1D optimization. Always distinguish 0/1 from fractional — they're different problems with different techniques: 0/1 needs DP because greedy fails on the integer constraint; fractional admits greedy by ratio because leftover capacity can always be filled. The counter-example — items (10,60), (20,100), (30,120), W=50 — should be at your fingertips to prove greedy fails on 0/1. Know that 0/1 Knapsack is NP-hard in general but DP-solvable in pseudo-polynomial time O(n·W); for huge W, switch to meet-in-the-middle (n ≤ 40), FPTAS (approximation), or branch-and-bound (exact with pruning). For variants: unbounded uses ascending iteration, bounded uses binary decomposition, multi-dimensional adds state dimensions. The mental model: 0/1 knapsack is the prototype for binary-choice DPs — the same skip-or-take template applies to subset sum, partition, equal-sum partition, target sum, and many other problems.