# Help with small program

Paul Watson pwatson at redlinepy.com
Mon Jan 1 01:14:13 CET 2007

```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}

```