Help with small program

[gokkog at yahoo.com]

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


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