<div dir="ltr">Thanks for the link it's really useful :)<br><br><div class="gmail_quote">On Mon, Sep 22, 2008 at 2:10 AM, Robert Berman <span dir="ltr"><<a href="mailto:bermanrl@embarqmail.com">bermanrl@embarqmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div bgcolor="#ffffff" text="#3333ff">
<font size="+1">That it is.</font><br>
<br>
Jaggo wrote:
<blockquote type="cite">
<div dir="ltr">Lol. And here I said to myself only, "What a nice
challenge".<br>
<br>
<div class="gmail_quote"><div><div></div><div class="Wj3C7c">On Sun, Sep 21, 2008 at 10:28 PM, Robert
Berman <span dir="ltr"><<a href="mailto:bermanrl@embarqmail.com" target="_blank">bermanrl@embarqmail.com</a>></span>
wrote:<br>
</div></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div><div></div><div class="Wj3C7c">
<div bgcolor="#ffffff" text="#3333ff">
<font size="+1">A very interesting problem. Given this is
homework, I
am not sure what it is you want.<br>
<br>
Do you want the solution coded and tested?<br>
Do you want this to include two or three algorithms optimized for speed
as well as accuracy?<br>
<br>
I think the problem is well enough defined so that you do not need any
clarification of what it is your professor wants from you.<br>
<br>
If you would like some help finding a solution set, perhaps you would
consider submitting some of your own solutions and commentary as to
where your ideas are breaking down. Then, probably, a number of people
will jump in to help you.<br>
<font color="#888888"><br>
Robert<br>
</font></font>
<div>
<div><br>
<a href="mailto:btkuhn@email.unc.edu" target="_blank">btkuhn@email.unc.edu</a> wrote:
<blockquote type="cite">This is from the MIT Opencourseware intro
to computer
science course, which I've been working my way through. I understand
what needs to be done (I think), which is basically to test each
possibility and return the list of states with the most electoral votes
that can be paid for under the campaign budget. I am just at a loss as
to how to do it, and I've been thinking about it all weekend. Here is
the problem I am referring to. One assumption is that every $1 of money
spent in a state translates into a popular vote. Many thanks for any
suggestions. Also, the next part of the question asks to do the same
thing using "Branch and Bound", which I also anticipate having trouble
with. If I haven't described things sufficiently, the complete problem
is available at: <br>
<br>
<a href="http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-00Fall-2007/Assignments/index.htm" target="_blank">http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-00Fall-2007/Assignments/index.htm</a>
, problem 5. <br>
<br>
Complete and test this function according to her specification below.
Note that she was using exhaustive <br>
enumeration to compute the result. Your friend assured you that the
function needs no more than 5 additional <br>
lines of code. <br>
<br>
# Problem 2: Exhaustive enumeration <br>
def finance_campaign_ee(budget, free_states): """ <br>
Takes a budget, in dollars, and a list of available states, as a <br>
list of dictionaries. <br>
<br>
Computes and returns the list of states that maximizes the total <br>
number of electoral votes such that these states can be acquired <br>
on the budget. Returns an empty list if no states can be acquired. <br>
""" <br>
cheap_states=[] <br>
for s in free_states: <br>
if s['pop'] <= budget: <br>
cheap_states.append(s) <br>
<br>
# Base case <br>
if len(cheap_states)==0: <br>
res_list=[] <br>
# Recursive case <br>
else: <br>
curr_state=cheap_states[0] <br>
other_states=cheap_states[1:] <br>
<br>
inc_states=finance_campaign_ee( budget-curr_state['pop'], <br>
other_states) <br>
inc_states.append(curr_state) <br>
inc_evotes=total_evotes(inc_states) <br>
<br>
excl_states=finance_campaign_ee( budget, other_states ) <br>
excl_evotes=total_evotes(excl_states) <br>
<br>
# ... your code goes here ... <br>
res_list = return res_list <br>
<br>
_______________________________________________ <br>
Tutor maillist - <a href="mailto:Tutor@python.org" target="_blank">Tutor@python.org</a> <br>
<a href="http://mail.python.org/mailman/listinfo/tutor" target="_blank">http://mail.python.org/mailman/listinfo/tutor</a>
<br>
<br>
</blockquote>
</div>
</div>
</div>
<br></div></div>
_______________________________________________<div class="Ih2E3d"><br>
Tutor maillist - <a href="mailto:Tutor@python.org" target="_blank">Tutor@python.org</a><br>
<a href="http://mail.python.org/mailman/listinfo/tutor" target="_blank">http://mail.python.org/mailman/listinfo/tutor</a><br>
<br>
</div></blockquote>
</div>
<br>
</div>
</blockquote>
</div>
<br>_______________________________________________<br>
Tutor maillist - <a href="mailto:Tutor@python.org">Tutor@python.org</a><br>
<a href="http://mail.python.org/mailman/listinfo/tutor" target="_blank">http://mail.python.org/mailman/listinfo/tutor</a><br>
<br></blockquote></div><br><br clear="all"><br>-- <br>Cheers,<br>Vishwajeet<br><a href="http://www.singhvishwajeet.com">http://www.singhvishwajeet.com</a><br>
</div>