AlgoScope

Unbounded Knapsack

Items may repeat. The transition reads the same row instead of the previous one.

Dynamic programming, algorithm, intermediate
Item 1 at capacity 1: best of skip 0 and take 1 is 1.012345670i1i2i3i40000000001
Item 1 at capacity 1: best of skip 0 and take 1 is 1.012345670i1i2i3i40000000001

Knapsack: Unbounded, the same items

Decision, step 3 of 34

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.

How knapsack works

Cost

Best
O(n * W)
Average
O(n * W)
Worst
O(n * W)
Space
O(W)

Taught by the same lesson

Knapsack covers these too, in the same run.