# Problem 4: Subject Selection By Dynamic Programming
#
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)
    """
    memo = {}
    ## for dict method
    nameList = subjects.keys()
    nameList.sort()
##    
##    ## DeBug: make nameList shorter
##    nameList = nameList[20:25]

##    ## for class method
##    keyTuple = subjects.keys()
##    workList = []
##    valList = []
##    for n in keyTuple:
##        workList.append(subjects[n][WORK])
##        valList.append(subjects[n][VALUE])
    
    ## set up index
    i = len(nameList) - 1
    #i = len(keyTuple) - 1

    ## for dict method
    courseList = dpAdvisorHelperNoTup(subjects, i, nameList, maxWork, memo)
    #courseList = dpAdvisorHelper(workList, valList, i, maxWork, memo)
    
    ## DeBug
    #print courseList

    ## Change courseList to dictionary returning (value, work) tuple
    courseDict = {}
    for j in courseList[1]:
        courseDict[nameList[j]] = (subjects[nameList[j]][VALUE] , subjects[nameList[j]][WORK] )
##    for j in courseList[1]:
##        courseDict[keyTuple[j]] = ( valList[j] , workList[j] )
    return courseDict


def dpAdvisorHelperNoTup(subjects, i, nameList, aWork, memo):
    """ Takes a subjects dictionary, an order list of names that can be entered as
    keys in the subject dictionary, which will output (value, work), a starting
    index, i, the maximum amount of work, aWork, and a memo dictionary that
    takes (i, aWork) as a key """
    try:
        memo[(i, aWork)]
        return memo[(i, aWork)]
    except KeyError:
        if i == 0:
            if subjects[nameList[i]][WORK] <= aWork:
                ## memo returns list including total value achieved
                ## and another list that includes all indexes to recall
                ## the subjects that were used
                ## if i = 0 is included, memo will return [ value, [0]]
                memo[(i, aWork)] = [ subjects[nameList[i]][VALUE], [i] ]
                return [ subjects[nameList[i]][VALUE], [i] ]
            else:
                ## if i = 0 is not included, memo returns 0 with
                ## an empty list
                memo[(i, aWork)] = [0, []]
                return [0, []]
        without_i = dpAdvisorHelperNoTup(subjects, i - 1, nameList, aWork, memo)[:]
        if subjects[ nameList[i] ][WORK] > aWork:
            memo[(i, aWork)] = without_i[:]
            return without_i[:]
        else:
            with_i = dpAdvisorHelperNoTup( subjects, i - 1,  nameList, aWork - subjects[ nameList[ i ]][WORK], memo )
            with_i[0] = with_i[0] + subjects[ nameList[ i]][VALUE]
            #print "Pre append: with_i =",with_i,"i =",i
            ## new index, i, added to list of indecies
            # with_i[1] = with_i[1].append(i) results in with_i[1] == NoneType
            # have to do it the below way
            temp = with_i[1][:]
            temp.append(i)
            with_i = [with_i[0] , temp[:]]
        if with_i[0] > without_i[0]:
            memo[(i, aWork)] = with_i[:]
            return with_i[:]
        else:
            memo[(i, aWork)] = without_i[:]
            return without_i[:]