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

Question

我一直在研究OCW的贪心算法。

到目前为止，我有这个:

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。

Answer 1

既然这是家庭作业，我们不应该直接给出答案。下面是一些提示:

• 查看sorted()，按顺序对"最佳"候选人进行排序。
• 使用"关键函数"或"cmp函数"传递价值度量。
• 在结果列表中循环累积结果，直到达到"max"。

这里有一个资源可以让你开始:

• https://docs.python.org/2.7/howto/sorting.html