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