#
# Problem 4: Subject Selection By Dynamic Programming
#

bSubset = []
bValue = 0


def dpAdvisorHelper(w,v,i,aW,m):
    ##Go down branch, hold subjects, compare to bestSubset.
    ##Let's hope this works.
    ##Also, this is proof that programming is best late at night, lol
    global bSubset
    global bValue

    try: return m[(i,aW)]
    except KeyError:

        if i == 0: #Base case
            if bSubset == []: bSubset = [0]
            if w[i] <= aW: #Take
                m[(i,aW)] = v[i],[i]
                return v[i],[i]
            else: #Don't take
                m[(i,aW)] = 0,[]
                return 0,[]

        ##Going down the branches
        without_iS = []
        with_iS = []
        without_i,without_iS = dpAdvisorHelper(w,v,i-1,aW,m)
        if w[i] > aW: #No space left, can't include i
            m[(i,aW)] = without_i, without_iS[:]
            return without_i,without_iS[:]
        with_i,with_iS = dpAdvisorHelper(w,v,i-1,aW-w[i],m)
        with_i += v[i] #Adds the value of i
        with_iS.append(i) #Adds i to subset

        ##Choose new bSubset, if a larger value
        if max(with_i,without_i) >= bValue:
            print bSubset,bValue
            if with_i >= without_i:
                m[(i,aW)] = with_i, with_iS[:]
                bValue = with_i
                bSubset = with_iS[:]
                return with_i,with_iS[:]
            else:
                m[(i,aW)] = without_i,without_iS[:]
                bValue = without_i
                bSubset = without_iS[:]
                return without_i,without_iS[:]
        else: #Subset is less than bSubset
            if with_i >= without_i:
                m[(i,aW)] = with_i,with_iS[:]
                return with_i,with_iS[:]
            else:
                m[(i,aW)] = without_i,with_iS[:]
                return without_i,without_iS[:]

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)
    """
    # TODO...
    global bSubset
    global bValue

    v = []
    w = []
    subjectList = []
    for a in subjects:
        v.append(subjects[a][VALUE])
        w.append(subjects[a][WORK])
        subjectList.append(a)
    i = len(subjectList)-1
    aW = maxWork
    m = {}
    value,bSubset = dpAdvisorHelper(w,v,i,aW,m)
    print bSubset
    print bValue

    schedule = {}
    for a in bSubset:
        schedule[subjectList[a]] = subjects[subjectList[a]]
    return schedule

#
# Problem 5: Performance Comparison
#
def dpTime():
    """
    Runs tests on dpAdvisor and measures the time required to compute an
    answer.
    """
    # TODO...

    #lol = bruteForceAdvisor(SUBJECTS, 8)
    ## 8 = 9.5 seconds
    ## 9 = 26 seconds
    ## 10 = 71 seconds
    ## 11 = 184 seconds
    #printSubjects(lol)
    lol = dpAdvisor(SUBJECTS, 8)
    printSubjects(lol)