Skip to content
Tutorials Center
My learning

Topics

Lesson 151 of 225 ยท Dynamic Programming

The 0/1 Knapsack Problem

Master the 0/1 knapsack problem in Python: brute force, the DP table, the 1D space trick, rebuilding the chosen items, subset sum, equal partition and target sum.

You are packing a backpack for a hike. Each item has a weight and a value (how much you want it). The bag can carry a limited total weight. Which items should you take to get the most value? You cannot take half of an item, and you cannot take the same item twice: each item is either in or out, 0 or 1. That is why this is the 0/1 knapsack problem.

Knapsack is the most famous dynamic programming problem because so many others are knapsack in disguise: splitting a pile of money fairly, hitting an exact target sum, choosing projects under a budget. Learn it well once and you will recognise it everywhere. We will start with brute force, build the DP table, shrink it to one row, recover the chosen items, and then solve three famous variants.

The problem

Given n items with weight[i] and value[i] and a capacity W, choose a subset whose total weight is at most W and whose total value is as large as possible.

TEXT
capacity W = 7
item   weight   value
  A       1       1
  B       3       4
  C       4       5
  D       5       7

Take C + B  -> weight 7, value 9
Take D + A  -> weight 6, value 8
Take D only -> weight 5, value 7

Notice that greedy by "value per weight" (A has 1.0, B 1.33, C 1.25, D 1.4) would pick D first, then A, for 8. The best answer is 9. Greedy fails for 0/1 knapsack, which is why we need DP (see greedy vs DP).

Brute force

Each of the n items is in or out, so there are 2^n subsets. We can try them all with recursion: at item i with remaining capacity cap, either skip the item or (if it fits) take it.

Python Brute force knapsack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For 4 items the recursion is tiny, but each added item roughly doubles the calls. At 40 items you would wait forever. Yet there are only n * (W + 1) different pairs (i, cap), so the same subproblems repeat: perfect for DP.

The DP table

State: dp[i][w] = the best value achievable using only the first i items with capacity w.

Transition for item i (1-based, with weight wt and value v):

  • Skip it: dp[i-1][w].
  • Take it (only if wt <= w): v + dp[i-1][w - wt].
  • dp[i][w] is the larger of the two.

Base: dp[0][w] = 0 for all w (no items, no value), and dp[i][0] = 0.

Answer: dp[n][W].

Rows are items, columns are capacities. Every cell depends on the row above it, so we fill row by row.

Python Knapsack DP table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the last row: it shows the best value for every capacity from 0 to 7 at once. Reading dp[n][5] gives the best for a smaller bag at no extra cost.

Complexity: n * W states and constant work each, so O(n * W) time and O(n * W) space. This is called pseudo-polynomial: it is polynomial in the number W, but W itself can be exponentially large in the number of bits needed to write it down. Knapsack is NP-hard in general (see P, NP and hard problems); the DP is fast only when the capacity is a reasonable size.

Rolling the table into one row

Row i depends only on row i - 1. We can keep a single list and update it in place, if we sweep the capacities from high to low:

TEXT
dp[w] = max(dp[w], v + dp[w - wt])      for w from W down to wt

Why backwards? When computing dp[w] we need the value of dp[w - wt] from the previous item's row. Going downward guarantees that smaller indexes have not been updated for this item yet. If you sweep upward, dp[w - wt] may already include the current item, so the item could be used twice. (That, by the way, is exactly the unbounded knapsack of the next lessons.)

Python One-row knapsack and the direction trap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With the buggy direction, a single item of weight 2 is "taken" three times in a bag of capacity 6, producing 30 instead of 10. Space is now O(W), time still O(n * W).

Which items did we take?

The best value is rarely the whole story: you want the actual list. With the full 2D table, walk backwards from dp[n][W]. If dp[i][w] == dp[i-1][w], item i was not needed, so move up. Otherwise item i was taken: record it and move to dp[i-1][w - weight].

Python Reconstructing the chosen items

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Reconstruction needs the full table (or stored decisions). If memory is tight and you only need the value, use the one-row version; if you need the items too, keep the table or a boolean "taken" grid.

Variant 1: subset sum

Question: given positive numbers and a target T, is there a subset that adds up to exactly T? This is knapsack with weight = value = number, but we only need yes/no, so the table holds booleans: can[s] is true if some subset sums to s.

TEXT
can[0] = True
for each number x:
    for s from T down to x:
        can[s] = can[s] or can[s - x]
Python Subset sum

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time O(n * T), space O(T). A neat Python trick uses an integer as a bitset: bits |= bits << x marks every reachable sum in one operation, and bits >> T & 1 reads the answer.

Variant 2: partition equal subset sum

Question: can you split a list into two groups with equal sums? If the total is odd, no. Otherwise it is exactly subset sum with target total / 2: if one group reaches half, the rest also makes half.

Variant 3: target sum (counting)

Question: put a + or - in front of each number so the expression equals a target. How many ways? Let P be the sum of the numbers marked + and N the sum of those marked -. Then P - N = target and P + N = total, so P = (total + target) / 2. Counting sign assignments reduces to counting subsets with sum P: change or to + in subset sum.

Python Partition and target sum

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For [1,1,1,1,1] and target 3 we need P = (5 + 3) / 2 = 4 ones marked plus, and C(5, 4) = 5 ways to choose which one is minus. Zeros are a good test: each 0 can be +0 or -0, doubling the count, which the subset-count handles automatically because x = 0 doubles every entry.

Memoized form and when it wins

If most (i, cap) pairs are never reached (a huge capacity with few useful combinations), top-down memoization computes only what it needs. With functools.cache it is a three-line change to the brute force:

Python Memoized knapsack with functools.cache

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Complexity summary

Version Time Space Gives items?
Brute force O(2^n) O(n) yes
2-D table O(n * W) O(n * W) yes (walk back)
1-D row O(n * W) O(W) no (value only)
Bitset subset sum O(n * T / word size) O(T) bits no

Common mistakes

  • Iterating capacities upward in the 1-D version and accidentally allowing an item to be reused.
  • Starting the inner loop at 0 and indexing dp[w - wt] with a negative number (Python silently wraps around to the end of the list!). Start at wt.
  • Forgetting dp[0] = True (or 1 when counting) in subset-sum style DPs: nothing can ever become reachable.
  • Using greedy by ratio for the 0/1 version; it is only correct for the fractional knapsack (see greedy problems).
  • Ignoring pseudo-polynomial size. A capacity of 10^9 makes W + 1 cells impossible; look at the other dimension, or use meet in the middle (see Meet in the Middle).

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In the 0/1 knapsack table, what does dp[i][w] represent?

    Each cell answers a smaller version of the same question: the first i items and a bag of size w.
  2. 2. Why must the 1-D knapsack loop over capacities from high to low?

    Going downward means dp[w - wt] still holds the value from before the current item, so the item cannot be counted twice.
  3. 3. What is the time complexity of the table solution, and why is it called pseudo-polynomial?

    Work is proportional to n times W, and W can be exponentially large in the number of digits needed to write it.
  4. 4. How does "partition equal subset sum" reduce to subset sum?

    If one group sums to half of the total, the remaining numbers also sum to half.
  5. 5. What is the answer for weights [2], values [10], capacity 6 in a correct 0/1 knapsack?

    The only item can be taken once, so the best value is 10. Getting 30 means the loop direction allowed reuse.

Summary

  • 0/1 knapsack: each item is taken or not, maximizing value within a weight limit; brute force is O(2^n).
  • State dp[i][w] = best value from the first i items with capacity w; skip or take gives O(n * W) time.
  • A single row works if capacities are swept from high to low; sweeping upward turns it into unbounded knapsack.
  • Walk back through the table to recover which items were chosen.
  • Subset sum, equal partition and target sum are knapsack with booleans or counts instead of values.
  • The running time depends on the numeric size of the capacity, so it is pseudo-polynomial.

Next: Unbounded Knapsack and Coin Change