A community for students.
Here's the question you clicked on:
 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.
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

mattc
 5 years ago
Best ResponseYou've already chosen the best response.0In 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?

mattc
 5 years ago
Best ResponseYou've already chosen the best response.0so 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(index1, maxWork, valuework) if valuework[index][WORK] > maxWork: return without_i else: with_i = valuework[index][VALUE] + dpAdvisorHelper(index1, maxWork  valuework[index][WORK], valuework) return max(with_i,without_i)

mattc
 5 years ago
Best ResponseYou've already chosen the best response.0now i just have to figure out how too keep track of the subjects used.

mattc
 5 years ago
Best ResponseYou've already chosen the best response.0update.. 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(index1, maxWork, keys, subjects) if subjects[keys[index]][WORK] > maxWork: return (without_i,withoutC) else: temp = dpAdvisorHelper(index1, 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)

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0You 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.

mattc
 5 years ago
Best ResponseYou've already chosen the best response.0is there a better way to implement this using a dictionary then what i have currently in my previous post

anonymous
 5 years ago
Best ResponseYou've already chosen the best response.0Well 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.

mattc
 5 years ago
Best ResponseYou've already chosen the best response.0thats 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/electricalengineeringandcomputerscience/600introductiontocomputerscienceandprogrammingfall2008/videolectures/lecture13/lec13.pdf

mattc
 5 years ago
Best ResponseYou've already chosen the best response.0first 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.
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.