A community for students.
Here's the question you clicked on:
 0 viewing
anonymous
 5 years ago
Help in ps8, applying dynamic programming to brute force algorithm.
anonymous
 5 years ago
Help in ps8, applying dynamic programming to brute force algorithm.

This Question is Closed

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0def 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.

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0post 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
Ask your own question
Sign UpFind more explanations on OpenStudy
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
 Engagement 19 Mad Hatter
 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.