CodeCookbook

0/1 Knapsack

Time: O(nW)Space: O(nW)

Given items with weights and values, find the maximum value subset fitting in a knapsack of given capacity. Each item can be taken at most once (0/1 constraint).

SlowFast
1 / 42
DP Table
0
1
2
3
4
5
6
7
8
0
0
0
0
0
0
0
0
0
0
i1
0
0
0
0
0
0
0
0
0
i2
0
0
0
0
0
0
0
0
0
i3
0
0
0
0
0
0
0
0
0
i4
0
0
0
0
0
0
0
0
0
Inputs
#WeightValue
i1
i2
i3
i4
Phase
Fill Table
Description
Initialize 5×9 table. dp[i][w] = max value using first i items with capacity w.
Legend
Default
Active cell
Backtrack path
Header