AlgoScope

0/1 Knapsack

dp[i][w] = max(dp[i-1][w], dp[i-1][w - wt] + val). Each item is taken at most once.

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: 0/1 knapsack, capacity 7

Decision, step 3 of 34

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.

Leads to

Topics that need this one first.

Taught by the same lesson

Knapsack covers these too, in the same run.