DPDynamic Programming

Unbounded Knapsack

Maximize value under a capacity when every item may be taken any number of times — the 0/1 loop run forward.

weights | values | capacity — Three parts separated by pipes — e.g. "1,3,4,5 | 1,4,5,7 | 7". Up to 6 items, capacity ≤ 12

2/3

3/5

5/9

0	1	2	3	4	5	6	7	8	9
0	0	0	0	0	0	0	0	0	0

1/22A single row suffices because each item may be used any number of times: dp[c] may depend on dp[c - w] from the same row. Start with all zeros.

Cell being filledDependency readBase caseComputedReconstructed choice

1dp[0..W] = 0
2for c in 1 .. W:
3  for each item i with w[i] <= c:
4    dp[c] = max(dp[c], dp[c-w[i]] + v[i])
5return dp[W]

Variables

Complexity

best O(n·W)

avg O(n·W)

worst O(n·W)

space O(W)

Speed