From: Paolo Bonzini <bonzini@...>
Date: 2008-01-29T06:14:59+09:00
Subject: Re: Making Change (#154)


> should be limited since coin values are usually selected in a way to
> make it easy for people to give change.

Of course.  If every coin is a multiple of the immediately smaller
coin, the greedy algorithm is ok.  It happens to be with the euro
coins and Swiss franc coins (both have 200-100-50-20-10-5 cent coins,
and euro has additionally 2-1 cent coins), so there is probably a less
stringent sufficient condition.

> why there aren't any 17cent coins around -- which would be fun though.

There was a puzzle on DDJ asking for the optimal set of coins (i.e.
the one giving the smallest number of coins on average).  I don't have
it at hand but the results were weird, I recall.