dpAdvisorRevised

#'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
        s = subjects[i]
        withoutlist, withoutvalue = dpAdvisorHelper(subjects,maxWork, i+1, subsetWork, memo)
        if subsetWork + s[WORK] > maxWork:
            memo[(i, subsetWork)]=withoutlist,withoutvalue
            return memo[(i, subsetWork)]
        else:
            withlist, withvalue = dpAdvisorHelper(subjects, maxWork, i+1, subsetWork + s[WORK], memo)
            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)]