0

0/1 Knapsack

Medium

Each item is taken or skipped under a shared capacity. The table row i, column w is the best value using the first i items within weight w.

two dimensional DPtake or skip
TimeO(n * W)
SpaceO(W) after rolling the rows
Inputvalue:weight pairs | capacity
0
1
2
3
4
5
6
7
none
0
0
0
0
0
0
0
0
item 1 (v1/w1)
0
0
0
0
0
0
0
0
item 2 (v4/w3)
0
0
0
0
0
0
0
0
item 3 (v5/w4)
0
0
0
0
0
0
0
0
item 4 (v7/w5)
0
0
0
0
0
0
0
0
cell being filledcells it readsreconstructed answer

Row zero means no items available, so every capacity gives value zero.

1 / 34
for i in 1..n:
for w in 0..W:
skip = dp[i-1][w]
take = (wt[i] <= w) ? val[i] + dp[i-1][w - wt[i]] : -inf
dp[i][w] = max(skip, take)
Why it matters

Pseudo-polynomial: it scales with the numeric capacity, not just the item count.

Practise this
0/1 KnapsackMPartition Equal Subset SumMTarget SumMOnes and ZeroesM
Keyboard
space play← → stepr restartctrl K search

More in Dynamic Programming

Kadane (Maximum Subarray)
O(n)
Memoisation vs Brute Force
O(2^n) naive, O(n) memoised
Longest Common Subsequence
O(n * m)
Coin Change
O(coins * amount)
Longest Increasing Subsequence
O(n log n)
Minimum Path Sum
O(rows * cols)
Edit Distance
O(n * m)
Next visualiser
Longest Common Subsequence