🚀 Phases 1–5 are live — Days 1–17 cover the foundations and the algorithmic patterns. See the roadmap →
Day 14 - Dynamic ProgrammingPractice Questions0/1 Knapsack

0/1 Knapsack medium

Description

You have n items. Item i has weight weight[i] and value value[i]. You have a knapsack of capacity W. Pick a subset of items (each item at most once) that maximizes total value subject to total weight <= W.

This is the parent problem of an entire pattern — the answer to “should I take this item or skip it?” repeated n times.

Examples

> Case 1:
    weight = [1, 3, 4, 5],  value = [1, 4, 5, 7],  W = 7
    Output: 9
    Explanation: take items with weights 3 and 4 → values 4 + 5 = 9.
 
> Case 2:
    weight = [2, 3, 4, 5],  value = [3, 4, 5, 6],  W = 5
    Output: 7
    Explanation: take items 1 and 2 → 4 + 3 = 7.

Constraints

  • 1 <= n <= 1000
  • 1 <= weight[i], value[i] <= 1000
  • 1 <= W <= 10^4

State design

  1. What am I computing? dp[i][w] = max total value using any subset of the first i items with capacity exactly w (or less).

  2. Dimensions? Two — item index and capacity.

  3. Base cases? dp[0][w] = 0 for all w (no items → no value).

  4. Transition? At item i, two options:

    • Skip: carry the result without item i: dp[i - 1][w].
    • Take: add item i’s value, using weight[i] of the capacity: dp[i - 1][w - weight[i]] + value[i] — only valid if w >= weight[i].

    Pick the better: dp[i][w] = max(skip, take).

  5. Order? Increasing i, any order in w.

  6. Answer? dp[n][W].

Standard 2D solution

One-row space optimization

dp[i][w] only depends on dp[i - 1][w] and dp[i - 1][w - weight[i]]. Use one row and iterate the inner loop in reverse so that when we read dp[w - weight[i]], it still reflects the previous row.

⚠️

Iterate w in reverse, always. Iterating forward turns this into unbounded knapsack (each item reusable). The bug is silent — the code still runs, the answers are just wrong. This is the most-asked DP gotcha in interviews; if you remember nothing else from this page, remember the reverse loop.

Analysis

  • Time: O(n × W).
  • Space: O(n × W) for the 2D table, O(W) for the rolled-row version.

This is pseudo-polynomial — polynomial in W (the value of the capacity), not in the number of bits used to write W. For huge capacities it’s intractable; for the bounded-W constraints typical in interviews, it’s the right tool.

Longest Common SubsequencePartition Equal Subset Sum