0-1 Knapsack

Which features fit in this sprint, which files fit on this disk, which items fit in this truck: choosing a subset under a budget is the knapsack problem. It is NP-complete in general, yet for realistic capacities a simple table solves it exactly.

★ Lecture: DP_knapsack · Zaza Gamezardashvili▶ video intermediate⏱ 20 min read

←Builds on

7Fractional KnapsackWhen items cannot be split the ratio greedy fails, and a table is needed.10DP on GridsThe knapsack table is a grid: items down the side, capacities across the top.4Generating Subsets & PermutationsKnapsack DP replaces trying all 2ⁿ subsets of items with one take or skip decision per cell.

Leads to→

12P vs NP & Choosing an Algorithm0-1 knapsack is NP-hard; its O(n·W) table is fast only while W stays small.

1Learn 2Watch 3Play 4Check 5Practice

Learn

The idea, the mechanics and the cost.

01The problem, its variants, and why greedy fails

You are given N items; item i has weight wᵢ > 0 and value pᵢ > 0. Choose a subset whose total weight is at most the capacity W and whose total value is maximal. In general this is NP-complete, but for moderate W dynamic programming solves it.

The lecture lists the variants: fractional (any part of an item may be taken), 0-1 (one copy of each item), bounded (at most kᵢ copies), unbounded (any number), multiple-choice (one item per group) and multiple knapsacks.

Its example: W = 50, items 10, 20, 30 kg worth $60, $100, $120. In the fractional problem greedy by value per kg is optimal: $240. In the 0-1 problem greedy takes the first two ($160) and the third no longer fits, yet items 2 and 3 give $220. Whether an item is worth taking depends on what else fits, so we need DP.

02First without values: which weights are reachable?

Following the lecture, start with the simpler version. Store the weights in an array M and define

T(i, j) = 1 if some subset of the first i items weighs exactly j, else 0.

Base: T(0, 0) = 1 (choose nothing) and T(0, j) = 0 for j ≥ 1. Recurrence for i, j ≥ 1:

T(i, j) = T(i−1, j) when j < M[i];
T(i, j) = max(T(i−1, j), T(i−1, j−M[i])) when j ≥ M[i].

In words: weight j is reachable with i items if it was reachable without item i (skip it), or if j − M[i] was reachable and item i tops it up (take it).

Example: W = 16, M = 4, 5, 2, 7, 5. Row 1 has 1s at 0 and 4. For item 2 (M[2] = 5) every 1 of row 1 is copied down and also shifted by +5, giving 0, 4, 5, 9: no items, item 1, item 2, or both.

03The full table and recovering the answer

Repeat for all five items. In the last row every weight from 0 to 16 is reachable except 1, 3, 8 and 15 (the slide lists only 3, 8 and 15; 1 is missing there). The heaviest load that fits is the rightmost 1 of the last row: 16.

To find which items give it, the lecture walks back from that cell:

if the cell above also holds 1, the weight was reachable without this item, so move up to the same column;
if the cell above holds 0, this item must be taken: move up one row and left by its weight.

From (5, 16): above is 1, go up. At (4, 16): above is 0, so item 4 (weight 7) is taken, jump to (3, 9). Above is 1, go up to (2, 9). Above is 0: item 2 (weight 5) is taken, jump to (1, 4). Above is 0: item 1 (weight 4) is taken, reaching (0, 0). Answer: items 1, 2, 4, and 4 + 5 + 7 = 16.

Indigo: the walk back from (5, 16). Red: weights that no subset can make.

04Adding values: pseudo-polynomial O(n·W)

With values the method is the same; the table just stores sums of values instead of 1s. K[i][w] = the best value using the first i items with total weight at most w:

K[i][w] = max(K[i−1][w], K[i−1][w−wᵢ] + pᵢ)

(the second option only when wᵢ ≤ w). The answer is K[n][W], and the walk back works as before: if K[i][w] equals the cell above, item i was skipped. On the lecture’s three items, with weights and capacity divided by 10 (weights 1, 2, 3, capacity 5), the corner is 220.

The cost is O(n·W). Algorithms whose cost is a polynomial in two variables like this are called pseudo-polynomial: polynomial in the *number* W, but exponential in the bits needed to write W down. They are fast when W is in the thousands or millions and hopeless when W = 10¹⁸, which is why knapsack stays NP-complete.

05One array: 0-1, unbounded and bounded

Row i only reads row i−1, so a single array dp[w] can replace the table. The loop direction then decides which variant you solve:

0-1: for each item, loop w from W down to wᵢ: dp[w] = max(dp[w], dp[w−wᵢ] + pᵢ). Going down, dp[w−wᵢ] still holds the value from before this item, so each item is used at most once.
unbounded: loop w up (the lecture’s last program loops over capacities outside and items inside). Now dp[w−wᵢ] may already include item i, so it can be taken again and again.
bounded (at most kᵢ copies): treat the item as kᵢ separate 0-1 items, or split it into copies of 1, 2, 4, … so only O(log kᵢ) items are added.

Memory drops to O(W). The reachability version works the same way with booleans, or with a bitset shifted by wᵢ, which is very fast.

The lecture's C++C++

Slide 14: K[i][w] is the best value using the first i items with capacity w, and each cell either skips item i or takes it and adds K[i-1][w-wt[i-1]].

#include <bits/stdc++.h>
using namespace std;
int knapSack(int W, int wt[], int val[], int n){
    int i, w;
    int K[n+1][W+1];
    for (i=0; i<=n; i++) {
        for (w=0; w <= W; w++) {
            if (i==0 || w==0) K[i][w]=0;
            else if (wt[i-1] <= w)
                K[i][w]=max(val[i-1]+K[i-1][w-wt[i-1]],K[i-1][w]);
            else
                K[i][w]=K[i-1][w];
        }
    }
    return K[n][W];
}
int main(){
    int i, n, val[20], wt[20], W;
    cin>>n>>W;  //n-number of items, w-size of knapsack
    for(i = 0;i < n; ++i){
        cin>>val[i]>>wt[i]; //value and weight of items
    }
    cout<<knapSack(W, wt, val, n);
    return 0;
}

Cost at a glance

Reachability table T or value table KO(n·W)

Memory with a single dp[w] arrayO(W)

Recover the chosen itemsO(n)

Remember

For 0-1 knapsack, row i of the table says what is achievable with the first i items, and each cell either copies the cell above (skip) or reads the row above, wᵢ columns to the left (take).
Walk back from the answer: a value that also appears just above means the item was skipped, otherwise it was taken and you jump left by its weight.
O(n·W) is pseudo-polynomial: great for moderate capacities, useless for huge ones, which is why knapsack is still NP-complete.

Watch

The lecture as a narrated explainer video.

▶

Watch the lecture, animated

The video follows the lecture slide by slide: the same example, the same notation. Use it before or after playing with the visualizer.

▶ Open the video page ▣ Open as presentation

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: This is the lecture’s table: watch each row copy the 1s from above and add new ones shifted by the item’s weight, then follow the walk back from column 16. Add values in “try your own” to see the K[i][w] version.

Interactive visualizerfocus here, then space ← →

Reachability table (W = 16), weights: 4, 5, 2, 7, 5

i\\j	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1 (w=4)	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
2 (w=5)	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
3 (w=2)	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
4 (w=7)	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
5 (w=5)	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

Chosen items

(none yet)

T[0][0] = 1: with zero items, only total weight 0 is reachable.

Pseudocode

 1 T[0][0] = 1   // weight 0 is always reachable 2 for i in 1..n:      // consider item i 3   for j in 0..W: 4     if T[i-1][j]==1: T[i][j]=1        // skip item i 5     if T[i-1][j]==1 and j+w[i]<=W: T[i][j+w[i]]=1  // take it 6 answer = rightmost 1 in row n 7 backtrack: T[i-1][j]==1 ? skip item i : take it, j -= w[i] 8 // with values p[i]: K[0][w] = 0 9 K[i][w] = max(K[i-1][w], K[i-1][w-w[i]] + p[i])  // skip or take10 answer K[n][W]; backtrack: K[i][w] != K[i-1][w] ⇒ item i taken

1 / 1

Check

Three questions. Pick an answer to see why.

Weights 3 and 5, W = 10 (reachability version). Which weights are reachable in the last row?

You use one array dp[w] for 0-1 knapsack but loop w upwards. What goes wrong?

n = 100 items, W = 10⁹. Is the O(n·W) DP a good idea?

Practice

Real problems to lock it in, easiest first.

LeetCodePartition Equal Subset Sum intermediate↗CSESMoney Sums intermediate↗CSESBook Shop intermediate↗LeetCodeCoin Change II intermediate↗CSESTwo Sets II advanced↗