What is the bad case in greedy algorithm for coin changing algorithm?

Question

The Coin changing problem is making change for n cents using the fewest number of coins.

Can you give a set of coin denominations for which the greedy algorithm does not yield an optimal solution. The set should include a penny so that there is a solution for every n.

Answer 1

Well, given 10, 7, 1 coins change 15:

15 = 10 + 1 + 1 + 1 + 1 + 1 // greedy  (6 coins)
15 =  7 + 7 + 1             // optimal (3 coins)

You can easily generate a greedy solution as much inefficient as you want: just let available coins be 1, N-1, N and try to change 2 * N - 2:

 N, 1, 1, ..., 1 // greedy  (N - 1 coins)
 N-1, N-1        // optimal (2 coins)

Now, make N being large