search
Table of Contents
Homework Assignment #15
Objective
To use dynamic programming to solve the coins problem by making optimal change.
Exercises
Show all work neatly.
Question 1
Consider the table below for making change using dynamic programming. Use the given denominations, and complete the empty cells on the right in order to calculate the optimal way of making change for 10 (units).
Amount: |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
d1=1 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
||||
d2=4 |
0 |
1 |
2 |
3 |
1 |
2 |
3 |
||||
d3=6 |
0 |
1 |
2 |
3 |
1 |
2 |
1 |
Question 2
Consider the table from question (1). Now extract the optimal change for 10 (units): which coins do you use?
Question 3
Now try a new coin system: [1,3,4]. (a) Make change for 6. Show your table. (b) Extract your answer: which coins do you use? © Would the greedy algorithm have given the same answer?
