[Tutor] Exhaustive Enumeration

[vishwajeet singh]

Thanks for the link it's really useful :)

On Mon, Sep 22, 2008 at 2:10 AM, Robert Berman <bermanrl at embarqmail.com>wrote:

>  That it is.
>
> Jaggo wrote:
>
> Lol. And here I said to myself only, "What a nice challenge".
>
> On Sun, Sep 21, 2008 at 10:28 PM, Robert Berman <bermanrl at embarqmail.com>wrote:
>
>>  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
>>
>>
>> _______________________________________________
>> Tutor maillist  -  Tutor at python.org
>> http://mail.python.org/mailman/listinfo/tutor
>>
>>
>
> _______________________________________________
> Tutor maillist  -  Tutor at python.org
> http://mail.python.org/mailman/listinfo/tutor
>
>


-- 
Cheers,
Vishwajeet
http://www.singhvishwajeet.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20080922/be2c9cde/attachment-0001.htm>