4. (25 points) Let A,-{ a, a2, , an } be a finite set of distinct coin types (e.g., ?,-50 cents, a,-25 cents, a,- 10 cents etc.). We assume each a is an integer and that ai > 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) Explain that if an l then there exists a finite set of coin types and a C for which there is no solution to the coin changing problem. (b) When an-1 a greedy solution to the problem will make change by using the coin types in the order ai, a2, ..., an. When coin type ai is being considered, as many coins of this type as possible will be given. Write an algorithm based on this strategy. solutions that use the minimum total number of coins. vields solutions with a minimum number of coins. (c) Give a counterexample to show that the algorithm in (b) doesn't necessarily generate (d) Show that if An-k"-1, k"-2,.., k for some k> 1 then the greedy method in (b) always