Friday, August 5, 2011

MIT 6.00 Problem Set 8 - Problem 2


The problem statement does not mention sorting. But sorting the entire dict would be helpful. And the comparator could be used with sorted() but since there is no mention of sorting the data set I leave it unsorted.  So this may be a completely wrong approach but I take two tuples at a time and whichever is best is added to the solution set where best is judged by the comparator.

Python Code:

def greedyAdvisor(subjects, maxWork, comparator):
    schedule = {} # initial solution
    firstSubject = {}
    odd = True
    work = 0    
    test = subjects.copy()
    for key in subjects.keys():
        if odd == True:
            firstSubject = subjects[key]
            odd = False
        else:
            odd = True
            if comparator(firstSubject, subjects[key]):
                if work + firstSubject[WORK] <= maxWork:
                    schedule[key] = firstSubject
                    work += firstSubject[WORK]
            else:
                if work + subjects[key][WORK] <= maxWork:
                    schedule[key] = subjects[key]
                    work += subjects[key][WORK]

    if test != subjects:
        print "SUBJECTS MUTATED"

    return schedule
Output:
cmpValue
Course  Value   Work
======  ====    =====
12.05   7       1
14.01   6       1
22.12   10      18
6.09    8       4
7.11    7       4
7.15    3       3
7.17    10      1
7.19    10      5
8.10    4       6
8.14    3       7
8.18    4       10

Total Value:    72
Total Work:     60

cmpWork
Course  Value   Work
======  ====    =====
12.03   2       1
14.01   6       1
22.12   8       15
6.09    8       4
7.11    7       4
7.15    3       3
7.17    10      1
7.19    10      2
8.10    4       6
8.14    3       7
8.16    2       6
8.18    4       10

Total Value:    67
Total Work:     60

cmpRatio
Course  Value   Work
======  ====    =====
12.03   2       1
12.05   7       1
14.01   6       1
22.12   10      18
6.09    8       4
7.02    3       2
7.11    7       4
7.15    3       3
7.17    10      1
7.19    10      2
8.14    3       7
8.16    2       6
8.18    4       10

Total Value:    75
Total Work:     60

No comments:

Post a Comment