0/1 Knapsack
Dynamic ProgrammingavgO(n·W)worstO(n·W)spaceO(n·W)
0
1
2
3
4
5
6
7
8
9
10
∅
#1 w1 v1
#2 w3 v4
#3 w4 v5
#4 w5 v7
#5 w2 v3
Cell [i][c] will hold the best value using only the first i items with capacity c
1 / 64
Items5/8
#weightvalue
#1
#2
#3
#4
#5
Capacity10
How it works
Picks the subset of items with the highest total value whose total weight fits the capacity, where each item is either taken whole or left behind. Cell [i][c] holds the best value using only the first i items with capacity c: either skip item i, or take it and add its value to the best answer for the remaining capacity. Walking back up the rows reveals which items were taken.
Complexity
- Best
- O(n·W)
- Average
- O(n·W)
- Worst
- O(n·W)
- Space
- O(n·W)