Unbounded Knapsack
Items may repeat. The transition reads the same row instead of the previous one.
Knapsack: Unbounded, the same items
Item 1 (weight 1, value 1) at capacity 1. Skip: 0 from above. Take: 1 + 0 from this row at capacity 0 = 1. Best: 1, take.
Cost
- Best
- O(n * W)
- Average
- O(n * W)
- Worst
- O(n * W)
- Space
- O(W)
Before this
Related
Taught by the same lesson
Knapsack covers these too, in the same run.