Coins (26 Feb 2003)
What's special about the value of English coins that a greedy algorithm for picking them seems to work right? If you only had 1p, 20p and 50p, and you were trying to make 60p then a greedy algorithm would get you a solution with 11 coins (50 + 10×1), while the best one does it in 3 (3×20). So a greedy solution doesn't work in the general case, but I can't find a counter example for English coins.
So, is there a counter example that I've missed, or is there something special about the value of English coins?
(English coins are 200p, 100p, 50p, 20p, 10p, 5p, 2p and 1p)