Knapsack 01 — DSA-30

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

What am I computing? dp[i][w] = max total value using any subset of the first i items with capacity exactly w (or less).
Dimensions? Two — item index and capacity.
Base cases? dp[0][w] = 0 for all w (no items → no value).
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).
Order? Increasing i, any order in w.
Answer? dp[n][W].

Try it yourself

⌨ 0/1 Knapsack — return the max value within capacity W

def knapsack(weight, value, W):
  # for each item, choose skip or take (if it fits); maximize total value
  pass

Hint

dp[i][w] = max(skip = dp[i-1][w], take = dp[i-1][w-weight[i]] + value[i] when it fits). Each item is used at most once.

Reveal solution

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 Subsequence Partition Equal Subset Sum

Finished this page?