A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 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?

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

    what are you having trouble with? When I worked on that problem, the memo was the hard part...

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

    I'm having trouble getting the dpAdvisor to work. Did you modify the bruteForceAdvisor to create dpAdvisor or just start from scratch?

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

    Is the memo the dictionary where the previous calls are stored?

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

    yes, that's the memo

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

    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.

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

    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]

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

    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.

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

    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

  9. 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.