dbwonders

dpAdvisor

May 22nd, 2012
57
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import time
  2. import decimal
  3.  
  4. SUBJECT_FILENAME = "subjects.txt"
  5. VALUE, WORK = 0, 1
  6. #
  7. # Problem 1: Building A Subject Dictionary
  8. #
  9.  
  10. def loadSubjects(filename):
  11.     """
  12.    Returns a dictionary mapping subject name to (value, work), where the name
  13.    is a string and the value and work are integers. The subject information is
  14.    read from the file named by the string filename. Each line of the file
  15.    contains a string of the form "name,value,work".
  16.  
  17.    returns: dictionary mapping subject name to (value, work)
  18.    """
  19.  
  20.     # How to combine strip_line and split_line
  21.     # Changed [1] and [2] work and value into integers for use later. Left [0]
  22.     # name as a string. Note affects sort
  23.     inputFile = open(filename)
  24.     subjects_dict={}
  25.     for line in inputFile:
  26.         strip_line=line.strip()
  27.         split_line=strip_line.split(',')
  28.         subjects_dict[(split_line[0])]=int(split_line[1]),int(split_line[2])
  29.     return subjects_dict
  30.  
  31. #
  32. #'DP memo[(i, subsetWork)]'  based on brute force
  33. #
  34.  
  35. def dpAdvisor(subjects, maxWork):
  36.     """
  37.    Returns a dictionary mapping subject name to (value, work), which
  38.    represents the globally optimal selection of subjects using a brute force
  39.    algorithm.
  40.  
  41.    subjects: dictionary mapping subject name to (value, work)
  42.    maxWork: int >= 0
  43.    returns: dictionary mapping subject name to (value, work)
  44.    """
  45.     nameList = subjects.keys()
  46.     tupleList = subjects.values()
  47.     bestSubset, bestSubsetValue = \
  48.             dpAdvisorHelper(tupleList, maxWork, 0, 0, {})
  49.     outputSubjects = {}
  50.     print bestSubset, bestSubsetValue
  51.     for i in bestSubset:
  52.         outputSubjects[nameList[i]] = tupleList[i]
  53.     return outputSubjects
  54.  
  55. def dpAdvisorHelper(subjects, maxWork, i, subsetWork, memo):
  56.  
  57.     try: return memo[(i, subsetWork)]
  58.     except KeyError:
  59.         # Hit the end of the list.
  60.         if i >= len(subjects):
  61.             memo[(i, subsetWork)]=[],0
  62.             return [],0
  63.         else:
  64.             s = subjects[i]
  65.             # Try including subjects[i] in the current working subset.
  66.             withlist, withvalue = dpAdvisorHelper(subjects, maxWork, i+1, subsetWork + s[WORK], memo)
  67.             if subsetWork + s[WORK] <= maxWork:
  68.                 withlist = [i] + withlist
  69.                 withvalue += s[VALUE]
  70.  
  71.             withoutlist, withoutvalue = dpAdvisorHelper(subjects,maxWork, i+1, subsetWork, memo)
  72.             if withvalue > withoutvalue:
  73.                 memo[(i, subsetWork)]= withlist, withvalue
  74.                 return memo[(i, subsetWork)]
  75.             else:  
  76.                 memo[(i, subsetWork)] = withoutlist, withoutvalue
  77.                 return memo[(i, subsetWork)]
  78.  
  79.  
  80. subjects = loadSubjects(SUBJECT_FILENAME)
  81. maxWork=30
  82.  
  83. print 'DP memo[(i,subsetWork)]'
  84. start = time.time()
  85. printSubjects(dpAdvisor(subjects, maxWork))
  86. finish = time.time()
  87. print 'time: ',(finish-start)*1
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×