anonymous
  • anonymous
Working on ps8 and having trouble with problem 4. Anybody have this one solved or able to discuss it?
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.
chestercat
  • chestercat
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
anonymous
  • anonymous
what are you having trouble with? When I worked on that problem, the memo was the hard part...
anonymous
  • anonymous
I'm having trouble getting the dpAdvisor to work. Did you modify the bruteForceAdvisor to create dpAdvisor or just start from scratch?
anonymous
  • anonymous
Is the memo the dictionary where the previous calls are stored?

Looking for something else?

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

More answers

anonymous
  • anonymous
yes, that's the memo
anonymous
  • anonymous
I think I redid it from scratch, except for the idea of having a recursive dpAdvisorHelper() that does the work. I made more explicit for me the left - right branching of the recursion just like in the lecture. This still was by far the hardest assignment for me because I had an evil bug lurking in my code that took me hours to find. I was keeping track of sets of courses in the memo using dictionary objects like in the rest of the problem set code. Then when I took the branch that added the current course to the set of courses being examined, I was modifying the dictionary object that had been returned by the recursive function, which was actually the same object as inside the memo, so I was mutating the left branch objects in my memo when I created the right branch objects. But at least I probably will remember how to use copy() next time.
anonymous
  • anonymous
This was really hard... I modified the code used in class for the knap sack problem: m={} schedule=[] listwo=[] listw=[] keys=subjects.keys() vals=subjects.values() values=[0]*len(vals) for i in range(len(vals)): values[i]=vals[i][VALUE] works=[0]*len(values) for i in range(len(vals)): works[i]=vals[i][WORK] def smart(values,works,i,aW,m): try: return m[(i,aW)] except KeyError: if i==0: if works[i]<=aW: listw=[] listw=listw+[i] m[(i,aW)]=[values[i],listw] return [values[i],listw] else: listwo=[] m[(i,aW)]=[0,listwo] return [0,listwo] without_i,listwo=smart(values,works,i-1,aW,m) if works[i]>aW: schedule=listwo m[(i,aW)]=[without_i,schedule] return [without_i,schedule] else: temp=smart(values,works,i-1,aW-works[i],m) withi=values[i]+temp[0] listw=[i]+temp[1] if max(without_i,withi)==withi: schedule=listw else: schedule=listwo res=[max(without_i,withi),schedule] m[(i,aW)]=res return res def smartAdviser(values,works,i,aW,m): for i in smart(values,works,i,aW,m)[1]: print subjects.keys()[i]
anonymous
  • anonymous
jdanayalator, thank you. That code was what I began to attempt, but then gave up when I realized the difficulty. Glad I got to see how it'd be done, and it ran soo much faster than the one I had.
anonymous
  • anonymous
This version is a bit shorter but I think it still works as a replacement for jdanayalator's smart. Please let me know if it has any bugs. def dpAdvisorHelper(v,w,i,aW,m): """ v : list of values w : list of work costs i : index '(length of subjects dictionary) - 1' aW: available Work m : memo Returns: A tuple with the max value in index 1 and the list of indexes in index 2. """ try: return m[(i, aW)] except KeyError: if i == 0: if v[i] <= aW: m[(i, aW)] = v[i], [i] return v[i], [i] else: m[(i, aW)] = 0, [] return 0, [] without_i, listWo = dpAdvisorHelper(v,w,i-1,aW,m) if w[i] > aW: m[(i, aW)] = without_i, listWo return without_i, listWo else: with_i, listW = dpAdvisorHelper(v,w,i-1,aW-w[i],m) with_i += v[i] listW.append(i) res = max((with_i, listW), (without_i, listWo)) listWo = [] listW = [] m[(i, aW)] = res return res

Looking for something else?

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