dbwonders

dpAdvisor

May 22nd, 2012
53
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