dpAdvisor

import time
import decimal

SUBJECT_FILENAME = "subjects.txt"
VALUE, WORK = 0, 1
#
# Problem 1: Building A Subject Dictionary
#

def loadSubjects(filename):
    """
    Returns a dictionary mapping subject name to (value, work), where the name
    is a string and the value and work are integers. The subject information is
    read from the file named by the string filename. Each line of the file
    contains a string of the form "name,value,work".

    returns: dictionary mapping subject name to (value, work)
    """

    # How to combine strip_line and split_line
    # Changed [1] and [2] work and value into integers for use later. Left [0]
    # name as a string. Note affects sort
    inputFile = open(filename)
    subjects_dict={}
    for line in inputFile:
        strip_line=line.strip()
        split_line=strip_line.split(',')
        subjects_dict[(split_line[0])]=int(split_line[1]),int(split_line[2])
    return subjects_dict

#
#'DP memo[(i, subsetWork)]'  based on brute force
#

def dpAdvisor(subjects, maxWork):
    """
    Returns a dictionary mapping subject name to (value, work), which
    represents the globally optimal selection of subjects using a brute force
    algorithm.

    subjects: dictionary mapping subject name to (value, work)
    maxWork: int >= 0
    returns: dictionary mapping subject name to (value, work)
    """
    nameList = subjects.keys()
    tupleList = subjects.values()
    bestSubset, bestSubsetValue = \
            dpAdvisorHelper(tupleList, maxWork, 0, 0, {})
    outputSubjects = {}
    print bestSubset, bestSubsetValue
    for i in bestSubset:
        outputSubjects[nameList[i]] = tupleList[i]
    return outputSubjects

def dpAdvisorHelper(subjects, maxWork, i, subsetWork, memo):

    try: return memo[(i, subsetWork)]
    except KeyError:
        # Hit the end of the list.
        if i >= len(subjects):
            memo[(i, subsetWork)]=[],0
            return [],0
        else:
            s = subjects[i]
            # Try including subjects[i] in the current working subset.
            withlist, withvalue = dpAdvisorHelper(subjects, maxWork, i+1, subsetWork + s[WORK], memo)
            if subsetWork + s[WORK] <= maxWork:
                withlist = [i] + withlist
                withvalue += s[VALUE]

            withoutlist, withoutvalue = dpAdvisorHelper(subjects,maxWork, i+1, subsetWork, memo)
            if withvalue > withoutvalue:
                memo[(i, subsetWork)]= withlist, withvalue
                return memo[(i, subsetWork)]
            else:
                memo[(i, subsetWork)] = withoutlist, withoutvalue
                return memo[(i, subsetWork)]


subjects = loadSubjects(SUBJECT_FILENAME)
maxWork=30

print 'DP memo[(i,subsetWork)]'
start = time.time()
printSubjects(dpAdvisor(subjects, maxWork))
finish = time.time()
print 'time: ',(finish-start)*1