There is a problem set from OCW, and from that, I was working on a greedy algorithm.
def greedyAdvisor(subjects, maxWork, comparator):
"""
Returns a dictionary mapping subject name to (value, work) which includes
subjects selected by the algorithm, such that the total work of subjects in
the dictionary is not greater than maxWork. The subjects are chosen using
a greedy algorithm. The subject's dictionary should not be mutated.
subjects: dictionary mapping subject name to (value, work)
maxWork: int >= 0
comparator: function taking two tuples and returning a bool
returns: dictionary mapping subject name to (value, work)
"""
greedySchedule = {}
currentWork = 0
nameList = []
workValueList = []
for name, workValue in subjects.items():
nameList.append(name)
workValueList.append(workValue)
while currentWork <= maxWork:
for i in range(len(workValueList) - 2):
for j in range(i, len(workValueList) - 1):
if comparator(workValueList[i], workValueList[j]):
bestKey = nameList[i]
bestTuple = workValueList[i]
currentWork += workValueList[i][WORK]
jWasPicked = False
else:
bestKey = nameList[j]
bestTuple = workValueList[j]
currentWork += workValueList[j][WORK]
jWasPicked = True
if currentWork > maxWork:
break
if jWasPicked:
break
if currentWork > maxWork:
break
greedySchedule[bestKey] = bestTuple
return greedySchedule
The comparators are:
VALUE = 0
WORK = 1
def cmpValue(subInfo1, subInfo2):
"""
Returns True if value in (value, work) tuple subInfo1 is GREATER than
value in (value, work) tuple in subInfo2
"""
val1 = subInfo1[VALUE]
val2 = subInfo2[VALUE]
return val1 > val2
def cmpWork(subInfo1, subInfo2):
"""
Returns True if work in (value, work) tuple subInfo1 is LESS than than work
in (value, work) tuple in subInfo2
"""
work1 = subInfo1[WORK]
work2 = subInfo2[WORK]
return work1 < work2
def cmpRatio(subInfo1, subInfo2):
"""
Returns True if value/work in (value, work) tuple subInfo1 is
GREATER than value/work in (value, work) tuple in subInfo2
"""
val1 = subInfo1[VALUE]
val2 = subInfo2[VALUE]
work1 = subInfo1[WORK]
work2 = subInfo2[WORK]
return float(val1) / work1 > float(val2) / work2
Whenever I execute this, it is only providing me with the subjects in the order they come in on the list. The dictionary I'm using is:
It always returns {'1.00': (7,7), '15.01': (9, 6)} when maxWork is 15. I'm using a particular printSubjects function that returns subjects in order based on the numerical order of the names. For instance, when I use it for the small_catalog, it is printing:
Clearly, this is a little flawed because 15.01 should be last but that isn't the point. The point is that it always prints in the order of this dictionary while limiting the workload to maxWork which is 15.
Back