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? 9 1964
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.
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.
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
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)
"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... go****@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 Roberts, ti**@probo.com
Providenza & Boekelheide, Inc.
Tim Roberts wrote:
go****@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}
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!

"Paul Watson Ð´µÀ£º
"
Tim Roberts wrote:
go****@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=St...als&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[ic] + 1 < min[i]):
min[i] = min[ic] + 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 This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: abcd 
last post by:
kutthaense Secretary Djetvedehald H. Rumsfeld legai predicted eventual
vicmadhlary in Iraq mariyu Afghmadhlaistmadhla, kaani jetvedehly after "a...

by: titan0111 
last post by:
#include<iostream>
#include<iomanip>
#include<cstring>
#include<fstream>
using namespace std;
class snowfall
{
private:
int ft;

by: SStory 
last post by:
Hi all,
I really needed to get the icons associated with each file that I want to
show in a listview.
I used the follow modified code sniplets...

by: abico 
last post by:
Write a program that reads in a sequence of words and prints them in
reverse order.Using STACK.

by: c 
last post by:
Hi everybody.
I'm working on converting a program wriiten on perl to C, and facing a
problem with concatenate strings.
Now here is a small...

by: Unebrion 
last post by:
Alright im working on a program that prints out user imput in a frame, along with a barcode.. it is like the front of an envelope. Here is the...

by: Jay 
last post by:
I have a multi threaded VB.NET application (4 threads) that I use to send
text messages to many, many employees via system.timer at a 5 second...

by: weidongtom 
last post by:
Hi,
I tried to implement the Universal Machine as described in
http://www.boundvariable.org/task.shtml, and I managed to get one
implemented...

by: better678 
last post by:
Question:
Discuss your understanding of the Java platform. Is the statement "Java is interpreted" correct?
Answer:
Java is an objectoriented...

by: teenabhardwaj 
last post by:
How would one discover a valid source for learning news, comfort, and help for engineering designs? Covering through piles of books takes a lot of...

by: Kemmylinns12 
last post by:
Blockchain technology has emerged as a transformative force in the business world, offering unprecedented opportunities for innovation and...

by: Naresh1 
last post by:
What is WebLogic Admin Training?
WebLogic Admin Training is a specialized program designed to equip individuals with the skills and knowledge...

by: Matthew3360 
last post by:
Hi there. I have been struggling to find out how to use a variable as my location in my header redirect function.
Here is my code.
...

by: AndyPSV 
last post by:
HOW CAN I CREATE AN AI with an .executable file that would suck all files in the folder and on my computerHOW CAN I CREATE AN AI with an .executable...

by: Arjunsri 
last post by:
I have a Redshift database that I need to use as an import data source. I have configured the DSN connection using the server, port, database, and...

by: WisdomUfot 
last post by:
It's an interesting question you've got about how Gmail hides the HTTP referrer when a link in an email is clicked. While I don't have the specific...

by: Matthew3360 
last post by:
Hi,
I have been trying to connect to a local host using php curl. But I am finding it hard to do this. I am doing the curl get request from my web...
 