Question :

Suppose that the coins of the fictional country of Combinatoria come in the de- nominations, d1, d2, . . . , dk, where d1 = 1 and the other di values form a set of distinct integers greater than 1. Given an integer, n > 0, the problem of making change is to find the fewest number of Combinatorian coins whose values sum to n.

(a) Give an instance of the making-change problem for which it is suboptimal to use the standard greedy algorithm, which repeatedly chooses a highest-valued coin whose value is at most n until the sum of chosen coins equals n. (writeup only)

(b) Implement the algorithm for the coin changing problem. Take as input a file with a set of denominations. Interactively ask the user for the amount he wants to make change for and print the number of coins and the actual change.