Let An = {a1, a2, ... , an} be a finite set of distinct coin types (for example a1 = 50 cents,a2 = 25 cents, a3 = 10 cents, and so on.) We can assume each ai is an integer and a1 > a2 >... > an. Each type is available in unlimited quantity. The coin-changing problem is to make up an exact amount C using a minimum total number of coins. C is an integer > 0.
a) Show that if an ≠ 1, then there exists a finite set of coin types and a C for which there is no solution to the coin-changing problem.
b) Show that there is always a solution when an = 1.
c) When an = 1, a greedy solution to the problems makes change by using the coin types in order a1, a2, ... , an. When coin type ai is being considered, as many coins of this type as possible are given. Write an algorithm based on this strategy. Show that this algorithm doesn't necessarily generate solutions that use the minimum total number of coins.
d) Show that if An = {kn-1, kn-2, ... , k0} for some k > 1, then the greedy method of part
(e) always yields solutions with a minimum number of coins.