0/1 Knapsack
dp[i][w] = max(dp[i-1][w], dp[i-1][w - wt] + val). Each item is taken at most once.
Knapsack: 0/1 knapsack, capacity 7
Item 1 (weight 1, value 1) at capacity 1. Skip: 0 from above. Take: 1 + 0 from the previous row at capacity 0 = 1. Best: 1, take.
Cost
- Best
- O(n * W)
- Average
- O(n * W)
- Worst
- O(n * W)
- Space
- O(W)
Pseudo-polynomial in W. O(W) space with a single row iterated right to left.
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
Knapsack covers these too, in the same run.