For what coinage systems does a greedy algorithm not work in providing change? For the United States coinage system, a greedy algorithm nicely allows for an algorithm that provides change in the least amount of coins. However, for a coinage system with 12 cent coins, a greedy algorithm would not work. For instance, change for 15 cents would be a 12 cent coin and 3 pennies (4 coins total) whereas a dime and a nickel (2 coins) would be optimal. In what types of coinage systems does the greedy algorithm not work?

Intuitively, the requirement for the greedy algorithm to work for a coinset $c_1