Re: Help with small program
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=Staticd1=tutorialsd2=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
Re: Help with small program
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
Re: Help with small program
Paul Watson wrote:
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.
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.
[...]
doit(70, (40,35,10))
70.0 requires 4 coins in hash {40: 1, 10: 3}
The point was that minimum number of coins in this case is actually
two, but the provided algorithm yields four.
-tom!
--
--
http://mail.python.org/mailman/listinfo/python-list
Re: Help with small program
[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 Roberts, [EMAIL PROTECTED] Providenza Boekelheide, Inc. -- http://mail.python.org/mailman/listinfo/python-list
Re: Help with small program
Paul Watson 写道： snip 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... -- http://mail.python.org/mailman/listinfo/python-list
Help with small program
Hello, I am a newbie with python, though I am having a lot of fun using
it. Here is one of the excersizes I am trying to complete:
the program is supposed to find the coin combination so that with 10
coins you can reach a certain amoung, taken as a parameter. Here is the
current program:
coins = (100,10,5,1,0.5)
anslist = []
def bar(fin, hist = {100:0,10:0,5:0,1:0,0.5:0}):
s = sum(x*hist[x] for x in hist)
l = sum(hist.values())
if s fin and l 10:
for c in coins:
if (s+c) = fin:
hist[c] += 1
bar(fin, hist)
hist[c] -= 1
elif l==10 and s==fin and not hist in anslist:
#p1
anslist.append(hist)
bar(50)
print anslist
The problem is that if I run it, anslist prints as [{0.5: 0, 1: 0, 10:
0, 100: 0, 5: 0}], which doesnt even add up to 50. When I check how
many times the program has reached the #p1 by sticking a print there,
it only reaches it once, and it comes out correct. why is it that this
result is replaced by the incorrect final one?
--
http://mail.python.org/mailman/listinfo/python-list
Re: Help with small program
smartbei schrieb:
Hello, I am a newbie with python, though I am having a lot of fun using
it. Here is one of the excersizes I am trying to complete:
the program is supposed to find the coin combination so that with 10
coins you can reach a certain amoung, taken as a parameter. Here is the
current program:
coins = (100,10,5,1,0.5)
anslist = []
def bar(fin, hist = {100:0,10:0,5:0,1:0,0.5:0}):
s = sum(x*hist[x] for x in hist)
l = sum(hist.values())
if s fin and l 10:
for c in coins:
if (s+c) = fin:
hist[c] += 1
bar(fin, hist)
hist[c] -= 1
elif l==10 and s==fin and not hist in anslist:
#p1
anslist.append(hist)
bar(50)
print anslist
The problem is that if I run it, anslist prints as [{0.5: 0, 1: 0, 10:
0, 100: 0, 5: 0}], which doesnt even add up to 50. When I check how
many times the program has reached the #p1 by sticking a print there,
it only reaches it once, and it comes out correct. why is it that this
result is replaced by the incorrect final one?
hist is stored in anslist as a pointer only, therfore the hist[c] -= 1
operates on the same dict as is stored in the anslist. Try the following
in the python interpreter:
a = { 'key' : 1 }
l = [a]
l[0]['key'] -= 1
a
instead use:
anslist.append(dict(hist.items))
which will copy the dict.
--
http://mail.python.org/mailman/listinfo/python-list
Re: Help with small program
Felix Benner wrote:
smartbei schrieb:
Hello, I am a newbie with python, though I am having a lot of fun using
it. Here is one of the excersizes I am trying to complete:
the program is supposed to find the coin combination so that with 10
coins you can reach a certain amoung, taken as a parameter. Here is the
current program:
coins = (100,10,5,1,0.5)
anslist = []
def bar(fin, hist = {100:0,10:0,5:0,1:0,0.5:0}):
s = sum(x*hist[x] for x in hist)
l = sum(hist.values())
if s fin and l 10:
for c in coins:
if (s+c) = fin:
hist[c] += 1
bar(fin, hist)
hist[c] -= 1
elif l==10 and s==fin and not hist in anslist:
#p1
anslist.append(hist)
bar(50)
print anslist
The problem is that if I run it, anslist prints as [{0.5: 0, 1: 0, 10:
0, 100: 0, 5: 0}], which doesnt even add up to 50. When I check how
many times the program has reached the #p1 by sticking a print there,
it only reaches it once, and it comes out correct. why is it that this
result is replaced by the incorrect final one?
hist is stored in anslist as a pointer only, therfore the hist[c] -= 1
operates on the same dict as is stored in the anslist. Try the following
in the python interpreter:
a = { 'key' : 1 }
l = [a]
l[0]['key'] -= 1
a
instead use:
anslist.append(dict(hist.items))
which will copy the dict.
Thanks!
BTW - its hist.items(), after that it worked.
--
http://mail.python.org/mailman/listinfo/python-list
Re: Help with small program
smartbei wrote:
Felix Benner wrote:
smartbei schrieb:
Hello, I am a newbie with python, though I am having a lot of fun using
it. Here is one of the excersizes I am trying to complete:
the program is supposed to find the coin combination so that with 10
coins you can reach a certain amoung, taken as a parameter. Here is the
current program:
coins = (100,10,5,1,0.5)
anslist = []
def bar(fin, hist = {100:0,10:0,5:0,1:0,0.5:0}):
s = sum(x*hist[x] for x in hist)
l = sum(hist.values())
if s fin and l 10:
for c in coins:
if (s+c) = fin:
hist[c] += 1
bar(fin, hist)
hist[c] -= 1
elif l==10 and s==fin and not hist in anslist:
#p1
anslist.append(hist)
bar(50)
print anslist
The problem is that if I run it, anslist prints as [{0.5: 0, 1: 0, 10:
0, 100: 0, 5: 0}], which doesnt even add up to 50. When I check how
many times the program has reached the #p1 by sticking a print there,
it only reaches it once, and it comes out correct. why is it that this
result is replaced by the incorrect final one?
hist is stored in anslist as a pointer only, therfore the hist[c] -= 1
operates on the same dict as is stored in the anslist. Try the following
in the python interpreter:
a = { 'key' : 1 }
l = [a]
l[0]['key'] -= 1
a
instead use:
anslist.append(dict(hist.items))
which will copy the dict.
Thanks!
BTW - its hist.items(), after that it worked.
An alternative.
cointypes = (100, 10, 5, 1, 0.5)
needed = {}
def coins(fin):
cur = fin
for c in cointypes:
v = int(cur / c)
if v 0:
needed[c] = v
cur -= v * c
if __name__ == '__main__':
coins(51)
print needed
coins(127)
print needed
--
http://mail.python.org/mailman/listinfo/python-list
Re: Help with small program
Better alternative.
cointype = (100, 10, 5, 1, 0.5)
def coins(fin):
needed = {}
for c in cointypes:
v, r = divmod(fin, c)
if v 0:
needed[c] = v
fin = r
return needed
if __name__ == '__main__':
print coins(51)
print coins(127)
print coins[12.5)
--
http://mail.python.org/mailman/listinfo/python-list
