Twelve At Capacity Eight

0/1 knapsack, capacity 8. dp[i][j] is the best value using only the first i items with capacity j, filled by dp[i][j]=max⁡(dp[i−1][j], dp[i−1][j−wi]+vi)dp[i][j] = \max(dp[i-1][j],\ dp[i-1][j-w_i] + v_i).

item weight value
1 3 4
2 4 5
3 2 3
4 5 8

The first three rows of the table:

i \ j 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0 0 0 4 4 4 4 4 4
2 0 0 0 4 5 5 5 9 9

What is dp[4][8], and which items achieve it?

A

9, from items 1 and 2 (weights 3 + 4)

B

12, from items 1 and 4 (weights 3 + 5)

C

11, from items 3 and 4 (weights 2 + 5)

D

15, from items 1, 3 and 4