anonymous
  • anonymous
Help in ps8, applying dynamic programming to brute force algorithm.
MIT 6.00 Intro Computer Science (OCW)
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
schrodinger
  • schrodinger
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
anonymous
  • anonymous
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.
anonymous
  • anonymous
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

Looking for something else?

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