Tim Roberts wrote: > [EMAIL PROTECTED] 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} -- http://mail.python.org/mailman/listinfo/python-list