Greedy algorithm for largest value in dictionaries in Python

Question

There is a problem set from OCW, and from that, I was working on a greedy algorithm.

So far I have this:

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:

small_catalog = {'6.00': (16, 8), '1.00': (7, 7), '6.01': (5, 3), '15.01': (9, 6)} 

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:

{'1.00': (7, 7), '15.01': (9, 6), '6.00': (16, 8), '6.01': (5,3)}

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.

Answer 1

Kindly refer to the below hints for your assignment:

• First, analyze the sorted() for ranking the "best" candidates in order.
• Then use a "key function" or "cmp function" to fill in the metric of merit.
• After that try to loop through the result list storing results until you hit "max".

Want to get certified in Python? Register for this complete Python Training course by Intellipaat.