[Tutor] Exhaustive Enumeration

[btkuhn at email.unc.edu]

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 <bermanrl at embarqmail.com>:

>       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
>
> btkuhn at email.unc.edu 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 at python.org
> http://mail.python.org/mailman/listinfo/tutor
>
>