cf.completefrontend
DYNAMIC PROGRAMMING · CORE

0/1 knapsack

Choose which items to take, each at most once, to get the most value without going over a capacity.

Time O(n × capacity)Space O(n × capacity)8 practice problemsStep-through picture

The idea

You have a bag that holds at most capacity units of weight, and a list of items. Each item has a weight and a value. You can take an item or leave it, but not take half of it or take it twice. That is why it is called 0/1. Which items give the most total value without going over the capacity?

Trying every combination means 2^n choices, about a million for 20 items. DP does better by asking smaller questions: "what is the best value using only the first i items with a bag of size cap?" Each answer comes from two smaller ones: skip item i, or take it.

The same table solves many problems that don't mention bags: can some numbers add up to exactly a target, can a list be split into two equal halves, how many subsets reach a total.

An everyday example

Packing a carry-on bag

You can bring a 7 kg carry-on and you have a laptop, a camera, books, and shoes, each with a weight and a value to you. For each item you ask one question: "is my best packing better with this item or without it?" Taking the item uses some weight, so you compare with the best packing of the other items in the space that is left.

How the example maps to the code
In the exampleIn the code
The bag's weight limitcapacity
Deciding about one item at a timeThe outer loop over i
Best packing of the first items in a smaller bagbest[i][cap]
Leaving the item at homebest[i - 1][cap]
Packing it and filling the rest of the space wellbest[i - 1][cap - weight] + value

From the slow way to 0/1 knapsack

  1. Start with brute force: try every subset of items, skip any that go over capacity, and keep the most valuable one. With n items there are 2^n subsets: 1,048,576 for 20 items, and about 1.1 trillion for 40. This is correct and far too slow.
  2. Write the same search as a chain of choices. Look at the items one at a time, and for each one either skip it or take it. After deciding about the first i items, the only things that matter for the rest are how many items are decided and how much room is left in the bag. Which exact items you took no longer matters.
  3. That changes the count of questions. Many different subsets end up at the same pair: "first i items decided, cap units of room". There are only (n + 1) × (capacity + 1) such pairs. For 40 items and a capacity of 1,000, that is 41,041 questions instead of a trillion subsets.
  4. So build a table best, where best[i][cap] is the most value you can get from the first i items in a bag of size cap. Each cell compares skipping item i, which reads the row above at the same cap, with taking it, which reads the row above at cap - weight and adds its value. Fill row by row. That loop is the 0/1 knapsack.

How it works

  1. Make a table best with n + 1 rows (no items, then items 1 to n) and capacity + 1 columns (bag sizes 0 to capacity), all 0.
  2. Row 0 stays 0: with no items, the best value is nothing.
  3. For each item i, read its weight and value.
  4. For each bag size cap, start with the value of skipping the item: best[i][cap] = best[i - 1][cap].
  5. If the item fits (weight <= cap), compare with taking it: best[i - 1][cap - weight] + value, and keep the larger.
  6. The answer is best[n][capacity]: all items considered, full bag size.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function knapsack(weights, values, capacity) {
  2. const n = weights.length;
  3. const best = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));
  4. for (let i = 1; i <= n; i++) {
  5. const weight = weights[i - 1];
  6. const value = values[i - 1];
  7. for (let cap = 0; cap <= capacity; cap++) {
  8. best[i][cap] = best[i - 1][cap];
  9. if (weight <= cap) {
  10. best[i][cap] = Math.max(best[i][cap], best[i - 1][cap - weight] + value);
  11. }
  12. }
  13. }
  14. return best[n][capacity];
  15. }

How fast it is

TimeO(n × capacity)
Extra memoryO(n × capacity)

One cell for every pair of item count and bag size, each filled with one comparison. The table can shrink to one row of capacity + 1 numbers if you loop the bag sizes from largest to smallest.

  • Best caseO(n × capacity)

    Any input, even when every item is too heavy: each of the n × (capacity + 1) cells is still visited once.

  • Average caseO(n × capacity)

    Any input: one copy and at most one comparison per cell.

  • Worst caseO(n × capacity)

    The same. The weights and values never change the number of cells.

Common mistakes

  • Reading best[i][cap - weight] (the same row) instead of best[i - 1][cap - weight]. That lets one item be taken many times.
  • Indexing items with weights[i] while rows start at 1, which skips the first item and reads past the end. Row i uses weights[i - 1].
  • Sorting by value per weight and taking the best ratio first. That greedy rule is only right when items can be cut into pieces.
  • Using this table when capacity is huge, such as 10^9. The table won't fit; look for a smaller dimension to index by.

When to use it

Look for these clues in a problem:

  • Each item can be used at most once and has a cost (weight, size, price, time).
  • There is a limit on the total cost, and you want the most value, or an exact total, or a count of ways.
  • The question is about choosing a subset: "pick some of these so that...".
  • The limit is a reasonably small whole number (up to a few thousand), so a table with one column per amount fits in memory.

Check yourself

Answer each one in your head first, then open it.

Why does the time depend on capacity and not just on n?

There is one cell per bag size, so a bigger capacity means a bigger table. This is called pseudo-polynomial: fast when the capacity number is small, slow when it is large, even with few items.

What changes if the taking case reads best[i][cap - weight] instead?

The rest of the bag could then already contain item i, so items can be taken many times. That turns it into the unbounded knapsack.

In the trace, why does item 4's row match item 3's row exactly?

At every size, taking item 4 is never better than what the first three items already give. At size 6 it ties at 14, and Math.max keeps the same number.

How many cells does the table have for 50 items and capacity 200?

51 × 201 = 10,251 cells, counting row 0 and bag size 0.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 8 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The table keeps one promise: once row i is filled, best[i][cap] is the most value from any subset of the first i items whose weights add up to at most cap. Row 0 is all zeros, which is right, because the only subset of no items is empty.

Filling row i keeps the promise. Take a best subset for (i, cap). If it leaves item i out, it is a valid subset of the first i - 1 items for the same cap, so its value is best[i - 1][cap]. If it uses item i, the other items in it are a subset of the first i - 1 items that fits in cap - weight, and they must be a best such subset; otherwise swapping in a better one would beat the best. So its value is best[i - 1][cap - weight] + value. The code computes both and keeps the larger.

Reading row i - 1 when taking the item is what enforces "at most once": the rest of the bag comes from items before i, so item i can't appear twice. Each row only reads the row above, so filling rows in order is safe. After the last row, the promise says best[n][capacity] is the answer.

Going deeper

4 more ideas

What each cell of the table means

best[i][cap] is the largest total value you can carry if you may only use the first i items and the bag holds cap units. Each row adds one more item to choose from. Each column is a different bag size. The bottom-right cell is the full question.

Why taking reads the row above

When you take item i, the rest of the bag must be filled from the earlier items only, because each item can be used once. That is row i - 1. Reading from row i instead would allow taking item i again, which is the unbounded knapsack.

How much work it does

There are (n + 1) * (capacity + 1) cells and each takes constant work, so the time is O(n * capacity). This is fast when the capacity is small. If the capacity is a billion, the table is too big, and other methods are needed.

Other questions on the same table

For "can some items add up to exactly target?", store true or false and use "or" instead of max. For "how many subsets add up to target?", store counts and add the two options. For a minimum, store Infinity for impossible cells and use Math.min.

Work it by hand

Every step in a table, with why

Pack a bag of capacity 6 from 4 items. Each row of the trace is one full row of the table, best[i], for bag sizes 0 to 6.

weights = [2, 1, 4, 3], values = [5, 3, 9, 6], capacity = 6

Stepiweightvaluebest[i], sizes 0 to 6What happensWhy
10--0, 0, 0, 0, 0, 0, 0No items yetRow 0 means "no items to choose from", so every bag size is worth 0.
21250, 0, 5, 5, 5, 5, 5Fits from size 2Sizes 0 and 1 are too small and copy the row above. From size 2 up, taking the item gives 0 + 5.
32130, 3, 5, 8, 8, 8, 8Size 3 takes bothAt size 3, taking item 2 adds 3 to best[1][2] = 5, which gives 8: both items fit together.
43490, 3, 5, 8, 9, 12, 14Sizes 4 to 6 improveAt size 6, taking it adds 9 to best[2][2] = 5, which gives 14. At size 4, it beats the old 8 by itself.
54360, 3, 5, 8, 9, 12, 14No cell changesAt size 6, taking it gives best[3][3] + 6 = 14, a tie with skipping. Math.max keeps 14, and line 14 returns best[4][6].

It returns 14. Two packings reach it: the items of weight 2 and 4 (5 + 9), or the items of weight 2, 1, and 3 (5 + 3 + 6). The loops end once the last item's row is filled.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
0/1 knapsackO(n × capacity)O(n × capacity)The capacity is a modest whole number, up to around a million cells in total, and you may need the chosen items.
One-row knapsackO(n × capacity)O(capacity)Only the best value is needed, and memory is tight.
Try every subsetO(2^n)O(n)About 20 items or fewer, with a capacity too big for any table.
Greedy by value per weightO(n log n)O(n)Only when items can be cut into fractions. For whole items it can miss the best packing.

Extra memory: O(n × capacity) for the full table. Each row only reads the row above, so one row of capacity + 1 numbers is enough if bag sizes are looped from largest to smallest: O(capacity).

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for 0/1 knapsack and the other approaches, on a scale where each line up is 10 times more steps.
  • 0/1 knapsack, One-row knapsack O(n × capacity)
  • Try every subset O(2^n)
  • Greedy by value per weight O(n log n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
0/1 knapsack1001 million1 trillion
One-row knapsack1001 million1 trillion
Try every subset1,024more than a quadrillionmore than a quadrillion
Greedy by value per weight339,96620 million

Inputs that need care

5 tricky inputs
capacity = 0
Every row has one cell, size 0. Only items of weight 0 fit, so the answer is the sum of their values, or 0 if there are none.
An item heavier than the bag
weight <= cap is never true for it, so its row is a copy of the row above. Nothing special is needed.
No items: weights = []
The table has only row 0, the loop never runs, and it returns 0.
A weight that is not a whole number, such as 2.5
best[i - 1][cap - 2.5] reads a cell that doesn't exist, which is undefined, and the result turns into NaN. Scale the weights to whole numbers first, for example by 10.
A huge capacity, such as 10^9
Each row would need a billion cells, which won't fit in memory. Look for another small dimension: if the values are small, index the table by total value instead and store the least weight for each.

Variations and follow-ups

Twists interviewers add

Hit a target exactly

For "can some items add up to exactly target?", store true or false instead of values, start with only ok[0][0] true, and combine skip and take with "or". Splitting a list into two equal halves is this question with target set to half the total.

Count the subsets

Store counts instead of values and add skip and take instead of taking the larger. count[0][0] = 1, since the empty subset makes a total of 0 in one way.

List the chosen items

Start at best[n][capacity] and walk up. If best[i][cap] equals best[i - 1][cap], item i was skipped. Otherwise it was taken, so record it and move to cap - weight. This needs the full table, not the one-row version.

Many items, huge capacity

With up to about 40 items and any capacity, split the items into two halves, list every subset of each half (about a million each), sort one list, and match pairs. This meet-in-the-middle method takes about 2^(n/2) steps instead of 2^n.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "each item at most once", a limit (weight, budget, size), and "maximize" or "is it possible". Problems about splitting numbers into two groups or reaching a target sum are often this table in disguise.
  • Describe the cell first: "best[i][cap] is the best value from the first i items with cap room". Then explain why taking reads row i - 1: it stops an item from being used twice.
  • Test with a tiny case by hand, such as two items and capacity 3, and also check an item that doesn't fit and a capacity of 0.
  • Expect "can you do it with one row?". Yes: loop cap from capacity down to weight, so best[cap - weight] still holds the old row's value when you read it. Looping upward would allow reuse.

Where frontend code uses it

The same idea in real UI code
  • Choosing which images, fonts, or scripts to preload within a fixed byte budget, picking the most useful set, is a 0/1 knapsack.
  • In a shopping cart, "use as much of a gift card as possible without going over" is the exact-total version on the item prices.
  • Splitting a list of tasks into two sprints of equal effort, or two dashboard columns of equal height, is the subset-sum version.

Related algorithms