使用 python 实现贪婪算法

问：

大家好，我正在用 coursera 学习算法工具箱课程，我对贪婪的算法实现感到困扰。任务 - “最大化战利品问题的价值。找到适合背包的物品的最大价值。输入：背包的容量 W 以及 n 种不同化合物的重量 （w1,...,wn） 和成本 （c1,..., cn）。输出：给定容量的背包中物品部分的最大总值：即 c1 ·F1 + ···+ 中文 ·fn 使得 w1·f1+···+wn·fn ≤ W 和 0 ≤ fi ≤ 1 表示所有 i（fi 是背包中第 i 件物品的分数）。

我的代码实现：

def Knapsack(number_of_compounds, knapsack_capacity):
    KnapsackCapacity = knapsack_capacity
    totalValue = 0
    bestItemIndex = 0
    itemWeights = []
    itemValues = []
    avarageWealth = []

    for value in range(0, number_of_compounds):
        temp = list(map(int, input().split()))
        itemValues.append(temp[0])
        itemWeights.append(temp[1])
        avarageWealth.append(itemValues[value] / itemWeights[value])
        temp.clear()

    while KnapsackCapacity > 0:
        if len(avarageWealth) > 1:
            bestItemIndex = avarageWealth.index(max(avarageWealth))
        elif len(avarageWealth) == 1:
            bestItemIndex = 0
        else:
            return totalValue

        if itemWeights[bestItemIndex] >= KnapsackCapacity:
            KnapsackCapacity -= 1
            totalValue += avarageWealth[bestItemIndex]
            itemWeights[bestItemIndex] -= 1
        else:
            KnapsackCapacity -= itemWeights[bestItemIndex]
            totalValue += itemValues[bestItemIndex]
            itemWeights.remove(itemWeights[bestItemIndex])
            itemValues.remove(itemValues[bestItemIndex])
            avarageWealth.remove(avarageWealth[bestItemIndex])

    return totalValue

number_of_compounds, knapsack_capacity = list(map(int, input().split()))
print("{:.3f}".format(Knapsack(number_of_compounds, knapsack_capacity)))

测试环境返回我

失败案例 #8/13：得到错误答案：215744.6596 预期：239607.438 （使用时间：0.01/5.00，内存使用：11366400/2684354560。