Help with small program

[Paul Watson]

Tim Roberts wrote:
> gokkog at yahoo.com wrote:
>> Interesting impl in Python! I am wondering what if the requirement is
>> to find the minimum number of coins which added to the "fin" sum...
> 
> Given the set of coins in the original problem (100, 10, 5, 1, 0.5), the
> solution it provides will always be optimal.  Even if we change this to
> American coinage (50, 25, 10, 5, 1), I believe it is still optimal.
> 
> It is certainly possible to construct a set of denominations for which the
> algorithm occasionally chooses badly.  For example, if you give it the set
> (40,35,10) and ask it to make change for 70, it will be suboptimal.

Tim,

Unless I am missing the point, the minimum number of coins from the set 
available will be chosen.  Surely this homework is past due by now.

$ cat coins.py
#!/usr/bin/env python
import sys

cointypes = (100, 10, 5, 1, 0.5)

def coins(fin, cointypes):
     needed = {}
     for c in cointypes:
         v, r = divmod(fin, c)
         if v > 0:
             needed[c] = int(v)
             fin = r
     return needed

def doit(fin, cointypes = cointypes):
     h = coins(fin, cointypes)
     print '%.1f requires %d coins in hash ' % (fin, sum(h.values())), h

if __name__ == '__main__':
     doit(51)
     doit(127)
     doit(12.5)
     doit(70, (40,35,10))

     sys.exit(0)

$ ./coins.py
51.0 requires 6 coins in hash  {1: 1, 10: 5}
127.0 requires 6 coins in hash  {1: 2, 10: 2, 100: 1, 5: 1}
12.5 requires 4 coins in hash  {0.5: 1, 1: 2, 10: 1}
70.0 requires 4 coins in hash  {40: 1, 10: 3}