A community for students.
Here's the question you clicked on:
 0 viewing
anonymous
 5 years ago
Working on ps8 and having trouble with problem 4. Anybody have this one solved or able to discuss it?
anonymous
 5 years ago
Working on ps8 and having trouble with problem 4. Anybody have this one solved or able to discuss it?

This Question is Closed

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0what are you having trouble with? When I worked on that problem, the memo was the hard part...

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0I'm having trouble getting the dpAdvisor to work. Did you modify the bruteForceAdvisor to create dpAdvisor or just start from scratch?

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0Is the memo the dictionary where the previous calls are stored?

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0I 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
 5 years ago
Best ResponseYou've already chosen the best response.0This 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,i1,aW,m) if works[i]>aW: schedule=listwo m[(i,aW)]=[without_i,schedule] return [without_i,schedule] else: temp=smart(values,works,i1,aWworks[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
 5 years ago
Best ResponseYou've already chosen the best response.0jdanayalator, 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
 5 years ago
Best ResponseYou've already chosen the best response.0This 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,i1,aW,m) if w[i] > aW: m[(i, aW)] = without_i, listWo return without_i, listWo else: with_i, listW = dpAdvisorHelper(v,w,i1,aWw[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
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.