Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def dpAdvisorHelper(subjects, maxWork, i, bestSubset, bestSubsetValue,
- subset, subsetValue, subsetWork, m):
- # Hit the end of the list.
- #print "program is called with:",i, subset, subsetValue, subsetWork
- print i,subsetValue,subsetWork
- if (i,subsetValue,subsetWork) in m:
- print "Found",i,subsetValue,subsetWork,"in m."
- return m[(i,subsetValue,subsetWork)]
- else:
- print "m not found."
- if i >= len(subjects):
- if bestSubset == None or subsetValue > bestSubsetValue:
- # Found a new best.
- m[(i,subsetValue,subsetWork)] = subset[:], subsetValue
- return subset[:], subsetValue
- else:
- # Keep the current best.
- m[(i,subsetValue,subsetWork)] = bestSubset, bestSubsetValue
- return bestSubset, bestSubsetValue
- else:
- s = subjects[i]
- # Try including subjects[i] in the current working subset.
- if subsetWork + s[WORK] <= maxWork:
- subset.append(i)
- bestSubset, bestSubsetValue = bruteForceAdvisorHelper(subjects,
- maxWork, i+1, bestSubset, bestSubsetValue, subset,
- subsetValue + s[VALUE], subsetWork + s[WORK])
- m[(i,subsetValue,subsetWork)] = bestSubset, bestSubsetValue
- subset.pop()
- bestSubset, bestSubsetValue = bruteForceAdvisorHelper(subjects,
- maxWork, i+1, bestSubset, bestSubsetValue, subset,
- subsetValue, subsetWork)
- m[(i,subsetValue,subsetWork)] = bestSubset, bestSubsetValue
- return bestSubset, bestSubsetValue
Advertisement
Add Comment
Please, Sign In to add comment