[ create a new paste ] login | about

Link: http://codepad.org/hVjl1rkR    [ raw code | fork ]

Asix3 - Python, pasted on Feb 7:
#
# 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 = {}
    nameList = subjects.keys()
    nameList.sort()
    
    ## DeBug: make nameList shorter
    nameList = nameList[20:25]
    
    ## set up index
    i = len(nameList) - 1

    courseList = dpAdvisorHelper(subjects, i, nameList, 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] )
    return courseDict

def dpAdvisorHelper(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)]
        print "Recalling that i,",i,", with aWork,",aWork,", gives:",memo[(i, aWork)]
        return memo[(i, aWork)]
    except KeyError:
        print "i @",i,"aWork @",aWork,". Current =",[nameList[i] , subjects[nameList[i]][VALUE], subjects[nameList[i]][WORK]]
        if i == 0:
            print "Last i . . ."
            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] ]
                print "returning:", memo[(i, aWork)]
                return [ subjects[nameList[i]][VALUE], [i] ]
            else:
                ## if i = 0 is not included, memo returns 0 with
                ## an empty list
                memo[(i, aWork)] = [0, []]
                print "returning:", memo[(i, aWork)]
                return [0, []]
        #print "subset =", subset,"and is of type:", type(subset)
        without_i = dpAdvisorHelper(subjects, i - 1, nameList, aWork, memo)
        print "without_i @",without_i,". i =",i
        if subjects[ nameList[i] ][WORK] > aWork:
            memo[(i, aWork)] = without_i
            print subjects[ nameList[i] ][WORK]," > ",aWork,". Returning ",without_i
            return without_i
        else:
            with_i = dpAdvisorHelper( subjects, i - 1,  nameList, aWork - subjects[ nameList[ i ]][WORK], memo )
            print "new with_i =", with_i
            ## value @ i added in separate step because with_i is a list of 2
            with_i[0] = with_i[0] + subjects[ nameList[ i]][VALUE]
            print "added value, with_i =",with_i
            #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]
            #print "Append is good! with_i =",with_i
            print " with_i =",with_i,", and without_i =,",without_i,". i =", i
        if with_i[0] > without_i[0]:
            #print "End: with_i =", with_i
            memo[(i, aWork)] = with_i
            print "with_i wins!"
            return with_i
        else:
            #print "End: without_i =",without_i
            memo[(i, aWork)] = without_i
            print "without_i wins!"
            return without_i


Create a new paste based on this one


Comments: