I'm actually not enrolled in the course; MIT puts some of its course
materials available online as a general resource. I am out of school
and trying to teach myself python on my own. I'm very much a beginner,
and since I'm not privy to the lectures or notes from this course I
have to fill in things from other sources. Basically, with respect to
this problem, I'm at a loss as to how to approach it. My first thought
was to use some sort of nested for loop structure to iterate through
each possible state combination, but I don't think this is possible,
since a for loop would just test for, for instance, (state 1 and 2,
state 1 and 3, state 1 and 4, etc.) and not (state 1 and 3, state 1 and
2 and 3, etc.). I could maybe make it work for a very small number of
states, but if you are taking 10 states as arguments I don't see a way
this could work. Also, the way the question is asked seems to imply
that the new code will go after the existing code, and also that it
will be only about five lines. I'm guessing that maybe some kind of
recursion is required but I really don't know, and recursion is a new
concept to me as well.
Thanks!
Quoting Robert Berman <[EMAIL PROTECTED]>:
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
