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
