Coin changing - my understanding is that if each denomination of coin is at least twice that of the next smaller, then greedy is optimal. Note to self - see if you can prove it.

That is the case for current US coinage, 1, 5, 10, 25, 50, 100, cents.