MattC
  • MattC
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.
MIT 6.00 Intro Computer Science (OCW)
jamiebookeater
  • jamiebookeater
See more answers at brainly.com
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.

Get this expert

answer on brainly

SEE EXPERT ANSWER

Get your free account and access expert answers to this
and thousands of other questions

MattC
  • MattC
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?
MattC
  • MattC
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)
MattC
  • MattC
now i just have to figure out how too keep track of the subjects used.

Looking for something else?

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

More answers

MattC
  • MattC
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)
anonymous
  • anonymous
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.
MattC
  • MattC
is there a better way to implement this using a dictionary then what i have currently in my previous post
anonymous
  • anonymous
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.
MattC
  • MattC
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
MattC
  • MattC
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.

Looking for something else?

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