Re: [Tutor] Exhaustive Enumeration

[Robert Berman]

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