A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • 5 years ago

Help in ps8, applying dynamic programming to brute force algorithm.

  • This Question is Closed
  1. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    def dpAdvisorHelper(subjects,maxWork,i,bestSubset,bestSubsetValue,subset,subsetValue,subsetWork,memo): try: return memo[tuple(subset)] except KeyError: # Hit the end of the list. if i >= len(subjects): memo[tuple(subset)] = subsetValue if bestSubset == None or subsetValue > bestSubsetValue: # Found a new best. return subset[:], subsetValue else: # Keep the current best. return bestSubset, bestSubsetValue else: s = subjects[i] # Try including subjects[i] in the current working subset. if subsetWork + s[WORK] <= maxWork: subset.append(i) memo[tuple(subset)] = subsetValue bestSubset, bestSubsetValue = dpAdvisorHelper(subjects, maxWork, i+1, bestSubset, bestSubsetValue, subset, subsetValue + s[VALUE], subsetWork + s[WORK],memo) subset.pop() bestSubset, bestSubsetValue = dpAdvisorHelper(subjects, maxWork, i+1, bestSubset, bestSubsetValue, subset, subsetValue, subsetWork,memo) return bestSubset, bestSubsetValue This returns an error that 'int' type isn't iterable. and I think the problematic line is: if subsetWork + s[WORK] <= maxWork: subset.append(i) memo[tuple(subset)] = subsetValue Because if I remove the memo part it works fine, but I lose the DP advantage I was going for. btw for those who don't remember the problem subset is a list not an int.

  2. anonymous
    • 5 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    post your code to dpaste.com, then post the link here- it will keep all the indentation and i'ts easier to read than on these posts. are you using windows/idle?? the traceback should tell you the offending line what data type is subset? if it is a list then this seems to work fine: memo[tuple(subset)] = 'something' how far is it recursing before it blows up? how are you calling it? maybe post dpAdvisor with the Helper (use dpaste.com) put a print statement in to print your variables to see what they are. I attached my functions in this post: http://openstudy.com/updates/4db64530c08f8b0bdc9531c3#/updates/4dabeb7ad6938b0bfe60a74d

  3. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.