A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

MattC

  • 5 years ago

I,m having trouble with problem set 8 problem 4. I can not figure out how to setup the parameters for the recursive function. Keeping track of the subjects is giving me trouble.

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

    In the example for the class where solve the max value problem. The method keeps returning the value until it bubbles up to the top with the max value finally being returned. In this case you want to keep track of not only the max value but all subjects that were added to get that value. creating a tuple with (dic, value) and then adding too it as you bubble up seems messy. Is this the wrong approach or is there a better way?

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

    so far i have gotten a basic version working which returns the max value. def dpAdvisor(subjects, maxWork): """ Returns a dictionary mapping subject name to (value, work) that contains a set of subjects that provides the maximum value without exceeding maxWork. subjects: dictionary mapping subject name to (value, work) maxWork: int >= 0 returns: dictionary mapping subject name to (value, work) """ # TODO... valuework = subjects.values() startindex = len(subjects)-1 print "Max value possible" print dpAdvisorHelper(startindex,maxWork,valuework) def dpAdvisorHelper(index, maxWork, valuework): if index ==0: if valuework[index][WORK] <= maxWork: return valuework[index][VALUE] else: return 0 without_i = dpAdvisorHelper(index-1, maxWork, valuework) if valuework[index][WORK] > maxWork: return without_i else: with_i = valuework[index][VALUE] + dpAdvisorHelper(index-1, maxWork - valuework[index][WORK], valuework) return max(with_i,without_i)

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

    now i just have to figure out how too keep track of the subjects used.

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

    update.. now have it working with subjects used, just need to implement dynamic programming. def dpAdvisor(subjects, maxWork): """ Returns a dictionary mapping subject name to (value, work) that contains a set of subjects that provides the maximum value without exceeding maxWork. subjects: dictionary mapping subject name to (value, work) maxWork: int >= 0 returns: dictionary mapping subject name to (value, work) """ # TODO... keys = subjects.keys() startindex = len(subjects)-1 print "Max value possible" print dpAdvisorHelper(startindex,maxWork,keys,subjects) def dpAdvisorHelper(index, maxWork, keys, subjects): if index ==0: if subjects[keys[index]][WORK] <= maxWork: return (subjects[keys[index]][VALUE],[keys[index]]) else: return (0,[]) without_i,withoutC = dpAdvisorHelper(index-1, maxWork, keys, subjects) if subjects[keys[index]][WORK] > maxWork: return (without_i,withoutC) else: temp = dpAdvisorHelper(index-1, maxWork - subjects[keys[index]][WORK],keys, subjects) with_i = subjects[keys[index]][VALUE] + temp[0] withC = [keys[index]] + temp[1] if max(with_i,without_i) == with_i: return (with_i, withC) else: return (without_i,withoutC)

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

    You need to remember that you're not just trying to figure out what the greatest value is, but you need to be able to keep track of the courses. Right now instead of returning a dictionary mapping course to value, you're returning only the maximum value. I suggest taking a look at the bruteForceAdvisor/Helper. Study it and see how it functions.

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

    is there a better way to implement this using a dictionary then what i have currently in my previous post

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

    Well damn, I've been working on it with bruteForceAdvisor as my template, but I've been running into an issue where it doesn't seem to be storing the most optimal solution in the dictionary. def dpAdvisor(subjects, maxWork): """ Returns a dictionary mapping subject name to (value, work) that contains a set of subjects that provides the maximum value without exceeding maxWork. subjects: dictionary mapping subject name to (value, work) maxWork: int >= 0 returns: dictionary mapping subject name to (value, work) """ nameList = subjects.keys() tupleList = subjects.values() m = {} bestSubset, bestSubsetValue = \ dpAdvisorHelper(tupleList, maxWork, 0, None, None, [], 0, 0, m) outputSubjects = {} for i in bestSubset: outputSubjects[nameList[i]] = tupleList[i] return outputSubjects def dpAdvisorHelper(subjects, maxWork, i, bestSubset, bestSubsetValue, subset, subsetValue, subsetWork, m): # Hit the end of the list. global numCalls numCalls += 1 try: return m[(i, subsetWork)][0], m[(i, subsetWork)][1] except KeyError: if i >= len(subjects): if bestSubset == None or subsetValue > bestSubsetValue: # Found a new best. m[(i, subsetWork)] = subset[:], subsetValue return subset[:], subsetValue else: # Keep the current best. m[(i, subsetWork)] = bestSubset, bestSubsetValue return bestSubset, bestSubsetValue else: s = subjects[i] if subsetWork + s[WORK] <= maxWork: subset.append(i) bestSubset, bestSubsetValue = dpAdvisorHelper(subjects, maxWork, i+1, bestSubset, bestSubsetValue, subset, subsetValue + s[VALUE], subsetWork + s[WORK], m) subset.pop() bestSubset, bestSubsetValue = dpAdvisorHelper(subjects, maxWork, i+1, bestSubset, bestSubsetValue, subset, subsetValue, subsetWork, m) m[(i, subsetWork)] = bestSubset, bestSubsetValue return bestSubset, bestSubsetValue I'll keep working on it, but it makes sense in my head and just simply isn't working for me in code.

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

    thats how i started, tried to use brute force as a template, but that had given me lots of trouble. Instead I studied the maxVal function on the in class handout. http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/video-lectures/lecture-13/lec13.pdf

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

    first thing i did was get it to return just the max value, then i worked on getting it to keep track of all the subjects in a list, finally once i had the function returning a list of subjects making a dictionary out of that was simple and then return the dictionary.

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