Name: ____________________________________________________ Alpha: _____________________
Describe help received: _________________________________________________________________
Per-problem assessment:
• 5 (Perfect): Correct solution
• 4 (Good effort): Good effort, solution may or may not be correct.
• 2 (Poor effort): Some basic misunderstandings demonstrated that could have
been cleared up by reading the notes or giving a serious try.
• 0 (No effort): No progress towards a solution.
Problem 0 (assessment: self_______ final_______)
Look at the description of the memoized 0/1 Knapsack
solution from the class notes. Below is shown and input problem and
the table created by the memoized algorithm in finding an optimal
solution for that problem. Use the table to work backwards and
figure out an optimum solution to this problem - i.e. which items
actually go in the knapsack. Be sure to show how the table is used!
10 : 2:3 3:7 4:8 4:9 3:2 ← Note: these are weight:value pairs
| n | cap |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 0 |
| 1 | 0 | -1 | 3 | 3 | 3 | -1 | 3 | 3 | -1 | -1 | 3 |
| 2 | -1 | -1 | 3 | 7 | -1 | -1 | 10 | 10 | -1 | -1 | 10 |
| 3 | -1 | -1 | -1 | 7 | -1 | -1 | 11 | 15 | -1 | -1 | 18 |
| 4 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | 16 | -1 | -1 | 20 |
| 5 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | 20 |