"Paul Watson 写道: " > 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}
To be explicit, the min coins question could be resolved with "dynamic programming". So it is not a pure python question. No, this is not a homework question. Well, it is somewhat academic: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg I wrote the following Python implementation akin to topcoder algorithm: #!/usr/bin/env python default_cointypes = (1, 3, 5) def mincoins(fin, cointypes = default_cointypes): needed = {} for c in cointypes: needed[c] = 0 min = {} for item in range(1, fin+1): min[item] = 2007 # suppose 2007 is the "infinity" min[0] = 0 for i in range(1, fin+1): for c in cointypes: if (c <= i and min[i-c] + 1 < min[i]): min[i] = min[i-c] + 1 needed[c] += 1 print fin, "==>", min[fin] print needed if __name__ == '__main__': mincoins(11) Probably there are things to be improved and there could be the pythonic way(s): Welcome your comments and ideas! Happy new year! Wenjie
-- http://mail.python.org/mailman/listinfo/python-list