dp.py

def dp(subjects, maxWork):
    m = [[(0,[]) for _ in range(maxWork + 1)] for _ in range(len(subjects) + 1)]

    name_list = subjects.keys()
    works = [i[WORK] for i in subjects.values()]
    vals = [i[VALUE] for i in subjects.values()]

    for	s in range(len(subjects)+1):
        for w in range(maxWork+1):
            if s == 0 or w == 0:
                continue
            elif works[s-1] <= w:
                next_max = get_max(vals[s-1], m[s-1][w-works[s-1]], s-1, m[s-1][w])
                m[s][w] = next_max
            else:
                m[s][w] = m[s-1][w]

    best = m[len(subjects)][maxWork]
    best_subjects = [name_list[i] for i in best[1]]
    return {s: subjects[s] for s in best_subjects}

def get_max(first_val, first_obj, first_parent, second_obj):
    if first_val + first_obj[0] > second_obj[0]:
        return (first_val + first_obj[0], first_obj[1] + [first_parent])
    return second_obj