dpAdvisorHelper

#            index   value work
# tupleList = 0    [ (16,   8),
#             1      ( 7,   7),
#             2      ( 5,   3),
#             3      ( 9,   6) ]
#
#            index   subject
# nameList =  0    [ '6.00',
#             1      '1.00',
#             2      '6.01',
#             3      '15.01' ]
#

def dpAdvisor(subjects, maxWork):
    """
    Returns a dictionary mapping subject name to (value, work) that contains a
    set of subjects that provides the maximum value without exceeding maxWork.

    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()
    memo = {}
    return dpAdvisorHelper(tupleList, len(tupleList)-1, maxWork, memo)

def dpAdvisorHelper(subjects, index, availableWork, memo):
    """
    Returns maximum value obtainable from available subjects with availableWork
    constraint

    subjects: list containing (value, work) tuples
    index: int >=0 and is the length of subjects list
    availableWork: int and is the workload constraint
    memo: dictionary mapping (index, availableWork) to subjects[index][VALUE]
    """

    try: return memo[(index, availableWork)]
    except KeyError:
        if index == 0:
            if subjects[index][WORK] <= availableWork:
                memo[(index, availableWork)] = subjects[index][VALUE]
                return subjects[index][VALUE]
            else:
                memo[(index, availableWork)] = 0
                return 0
        without_index = dpAdvisorHelper(subjects, index-1, availableWork, memo)
        if subjects[index][WORK] > availableWork:
            memo[(index, availableWork)] = without_index
            return without_index
        else:
            with_index = subjects[index][VALUE] + dpAdvisorHelper(subjects,
                        index-1, availableWork - subjects[index][WORK], memo)
        res = max(with_index, without_index)
        memo[(index, availableWork)] = res
        return res