CS 3341, Recitation Section, Problem list 7.  For Mar 9, 11.

The change-making problem: suppose you have m different coins of
denominations: d1 > d2 > ... > dm, and you want to use these
coins to make up an amount n.  You have an unlimited number of
coins of each denomination.

For example, if you have quarters, dimes, and pennies, then
d1 = 25, d2 = 10, d3 = 1.  If n = 30, then we can use 3 dimes
for change, or we can use 1 quarter and 5 pennies.

A greedy algorithm just tries the largest coins first, taking
as many of each coin as possible, and then proceeds to smaller coins.

Show that a greedy algorithm would give 1 quarter and 5 pennies
for change above.

If one wants to use a few coins as possible, then the greedy method
will not necessarily give the optimal solution.

Work on a dynamic programming solution to this problem, so that
in particular, in the case above we would arrive at the optimal
solution of 3 dimes.

The problem gets more interesting if there is not an unlimited
number of each type of coin.

References: See the text, page 300, problem 9,
and pages 303-304, along with problem 2 on page 309.