Python中字典最大值的贪心算法

Question

我一直在研究贪心算法，这个算法是来自于麻省理工学院的一个作业。

到目前为止，我写了这些：

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 subjects 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

比较器是：

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

每次我运行这个代码，它只会按照列表中出现的顺序给我显示科目。我使用的字典是：

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

当maxWork设为15时，它总是返回{'1.00': (7,7), '15.01': (9, 6)}
我使用了一个特定的printSubjects函数，它根据名字的数字顺序返回科目。例如，当我用它处理small_catalog时，它打印出

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

显然，这有点问题，因为15.01应该排在最后，但这不是重点。重点是它总是按照这个字典的顺序打印，同时把工作量限制在maxWork，也就是15。

数据结构计算机科学字典排序算法分析贪心算法比较器编程作业最大值问题

Python中字典最大值的贪心算法

1 个回答

撰写回答