Question

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.

Answer 1

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?

Answer 2

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)

Answer 3

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

Answer 4

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)

Answer 5

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.

Answer 6

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

Answer 7

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.

Answer 8

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

Answer 9

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.