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}
More information about the Python-list
mailing list