Guest User

failing attempt at dynamic programming

a guest
Mar 4th, 2012
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.71 KB | None | 0 0
  1. def dpAdvisorHelper(subjects, maxWork, i, bestSubset, bestSubsetValue,
  2.                             subset, subsetValue, subsetWork, m):
  3.     # Hit the end of the list.
  4.     #print "program is called with:",i, subset, subsetValue, subsetWork
  5.     print i,subsetValue,subsetWork
  6.     if (i,subsetValue,subsetWork) in m:
  7.         print "Found",i,subsetValue,subsetWork,"in m."
  8.         return m[(i,subsetValue,subsetWork)]
  9.     else:
  10.         print "m not found."
  11.         if i >= len(subjects):
  12.             if bestSubset == None or subsetValue > bestSubsetValue:
  13.                 # Found a new best.
  14.                 m[(i,subsetValue,subsetWork)] = subset[:], subsetValue
  15.                 return subset[:], subsetValue
  16.             else:
  17.                 # Keep the current best.
  18.                 m[(i,subsetValue,subsetWork)] = bestSubset, bestSubsetValue
  19.                 return bestSubset, bestSubsetValue
  20.         else:
  21.             s = subjects[i]
  22.             # Try including subjects[i] in the current working subset.
  23.             if subsetWork + s[WORK] <= maxWork:
  24.                 subset.append(i)
  25.                 bestSubset, bestSubsetValue = bruteForceAdvisorHelper(subjects,
  26.                         maxWork, i+1, bestSubset, bestSubsetValue, subset,
  27.                         subsetValue + s[VALUE], subsetWork + s[WORK])
  28.                 m[(i,subsetValue,subsetWork)] = bestSubset, bestSubsetValue
  29.                 subset.pop()
  30.             bestSubset, bestSubsetValue = bruteForceAdvisorHelper(subjects,
  31.                     maxWork, i+1, bestSubset, bestSubsetValue, subset,
  32.                     subsetValue, subsetWork)
  33.             m[(i,subsetValue,subsetWork)] = bestSubset, bestSubsetValue
  34.         return bestSubset, bestSubsetValue
Advertisement
Add Comment
Please, Sign In to add comment