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 .
| 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?
Sign in to answer questions and track your progress
Sign In