That it is.
Jaggo wrote:
Lol. And here I said to myself only, "What a nice
challenge".
On Sun, Sep 21, 2008 at 10:28 PM, Robert
Berman <[EMAIL PROTECTED]>
wrote:
A very interesting problem. Given this is
homework, I
am not sure what it is you want.
Do you want the solution coded and tested?
Do you want this to include two or three algorithms optimized for speed
as well as accuracy?
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.
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.
Robert
[EMAIL PROTECTED] wrote:
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:
http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-00Fall-2007/Assignments/index.htm
, problem 5.
Complete and test this function according to her specification below.
Note that she was using exhaustive
enumeration to compute the result. Your friend assured you that the
function needs no more than 5 additional
lines of code.
# Problem 2: Exhaustive enumeration
def finance_campaign_ee(budget, free_states): """
Takes a budget, in dollars, and a list of available states, as a
list of dictionaries.
Computes and returns the list of states that maximizes the total
number of electoral votes such that these states can be acquired
on the budget. Returns an empty list if no states can be acquired.
"""
cheap_states=[]
for s in free_states:
if s['pop'] <= budget:
cheap_states.append(s)
# Base case
if len(cheap_states)==0:
res_list=[]
# Recursive case
else:
curr_state=cheap_states[0]
other_states=cheap_states[1:]
inc_states=finance_campaign_ee( budget-curr_state['pop'],
other_states)
inc_states.append(curr_state)
inc_evotes=total_evotes(inc_states)
excl_states=finance_campaign_ee( budget, other_states )
excl_evotes=total_evotes(excl_states)
# ... your code goes here ...
res_list = return res_list
_______________________________________________
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
_______________________________________________
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
|
_______________________________________________
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
