[Tutor] Exhaustive Enumeration

[btkuhn at email.unc.edu]

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