#
# Problem 4: Subject Selection By 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)
"""
memo = {}
nameList = subjects.keys()
nameList.sort()
## DeBug: make nameList shorter
nameList = nameList[20:25]
## set up index
i = len(nameList) - 1
courseList = dpAdvisorHelper(subjects, i, nameList, maxWork, memo)
## DeBug
print courseList
## Change courseList to dictionary returning (value, work) tuple
courseDict = {}
for j in courseList[1]:
courseDict[nameList[j]] = (subjects[nameList[j]][VALUE] , subjects[nameList[j]][WORK] )
return courseDict
def dpAdvisorHelper(subjects, i, nameList, aWork,memo):
""" Takes a subjects dictionary, an order list of names that can be entered as
keys in the subject dictionary, which will output (value, work), a starting
index, i, the maximum amount of work, aWork, and a memo dictionary that
takes (i, aWork) as a key """
try:
memo[(i, aWork)]
print "Recalling that i,",i,", with aWork,",aWork,", gives:",memo[(i, aWork)]
return memo[(i, aWork)]
except KeyError:
print "i @",i,"aWork @",aWork,". Current =",[nameList[i] , subjects[nameList[i]][VALUE], subjects[nameList[i]][WORK]]
if i == 0:
print "Last i . . ."
if subjects[nameList[i]][WORK] <= aWork:
## memo returns list including total value achieved
## and another list that includes all indexes to recall
## the subjects that were used
## if i = 0 is included, memo will return [ value, [0]]
memo[(i, aWork)] = [ subjects[nameList[i]][VALUE], [i] ]
print "returning:", memo[(i, aWork)]
return [ subjects[nameList[i]][VALUE], [i] ]
else:
## if i = 0 is not included, memo returns 0 with
## an empty list
memo[(i, aWork)] = [0, []]
print "returning:", memo[(i, aWork)]
return [0, []]
#print "subset =", subset,"and is of type:", type(subset)
without_i = dpAdvisorHelper(subjects, i - 1, nameList, aWork, memo)
print "without_i @",without_i,". i =",i
if subjects[ nameList[i] ][WORK] > aWork:
memo[(i, aWork)] = without_i
print subjects[ nameList[i] ][WORK]," > ",aWork,". Returning ",without_i
return without_i
else:
with_i = dpAdvisorHelper( subjects, i - 1, nameList, aWork - subjects[ nameList[ i ]][WORK], memo )
print "new with_i =", with_i
## value @ i added in separate step because with_i is a list of 2
with_i[0] = with_i[0] + subjects[ nameList[ i]][VALUE]
print "added value, with_i =",with_i
#print "Pre append: with_i =",with_i,"i =",i
## new index, i, added to list of indecies
# with_i[1] = with_i[1].append(i) results in with_i[1] == NoneType
# have to do it the below way
temp = with_i[1][:]
temp.append(i)
with_i = [with_i[0] , temp]
#print "Append is good! with_i =",with_i
print " with_i =",with_i,", and without_i =,",without_i,". i =", i
if with_i[0] > without_i[0]:
#print "End: with_i =", with_i
memo[(i, aWork)] = with_i
print "with_i wins!"
return with_i
else:
#print "End: without_i =",without_i
memo[(i, aWork)] = without_i
print "without_i wins!"
return without_i