python - Python 中的贪心算法

Question

我希望 plunder(aList, c) 中的 c 等于 0。

List = [('Gold', 10, 500), ('Silver', 5, 200), ('Diamond', 2, 2000), ('Platinum', 20, 1000)]
aList = sorted(List, key =  lambda x : x[2]) # sort the list above

根据每个元组的第三个值给我排序列表。所以我得到:

[('Silver', 5, 200), ('Gold', 10, 500), ('Platinum', 20, 1000), ('Diamond', 2, 2000)]

我试图让 plunder(aList, c) 不断从 c 中减去每个元组 (2, 20, 10, 5) 的中间值，直到 c = 0。

这是我的代码:

List = [('Gold', 10, 500), ('Silver', 5, 200), ('Diamond', 2, 2000), ('Platinum', 20, 1000)]
aList = sorted(List, key =  lambda x : x[2]) # sort the list above

def plunder(aList, c):
    aList[-1] = list(aList[-1])
    i = aList[-1]
    r = 0
    if c > 0 and i[1] != 0:
        c -= 1
        i[1] -=1
        r += 1
        return plunder(aList, c-r)
    elif c == 0:
        pass
        print('Done')
    else:
        return plunder(aList[:-1], c-r)

plunder(aList, 10)

但是当我运行它时，它打印完成并且新列表是:

[('Silver', 5, 200), ('Gold', 10, 500), ('Platinum', 20, 1000), ['Diamond', 0, 2000]]

而且当我在 python shell 中键入 c 时，它告诉我 c 未定义。我该如何解决这些问题？

所以如果 c 值为 10。我的预期输出将是:

[('Silver', 5, 200), ('Gold', 10, 500), ['Platinum', 12, 1000], ['Diamond', 0, 2000]]

我从 10 (10 - 2 = 8) 中减去尽可能多的钻石，所以剩下 0 颗钻石。然后我从 20 个铂金中减去 8，铂金的重量变为 12(因为我拿了 8 个铂金。现在我的 c('容量')是 0。2 颗钻石 + 8 个铂金 = 10(这是我的 c)。

Answer 1

主要问题是您依赖 Python 的列表引用传递来就地修改列表。最初工作正常，但是当你到达

plunder(aList[:-1], c-r)

Python 创建列表的副本 并继续修改该副本。因此，在钻石耗尽后，您的原始列表保持不变(您点击了 else 部分)。

请注意，您可以在打印的 aList 中看到此行为，因为只有最后一个条目是 list 而所有其他条目都是元组。

[
 ('Silver', 5, 200), 
 ('Gold', 10, 500), 
 ('Platinum', 20, 1000), 
 ['Diamond', 0, 2000]   #Only list
]

如果在函数中加入print alist[-1]语句，就可以看得更清楚了。

['Diamond', 2, 2000]
['Diamond', 1, 2000]
['Diamond', 0, 2000]
['Platinum', 20, 1000]
['Platinum', 19, 1000]
['Platinum', 18, 1000]
['Platinum', 17, 1000]
['Platinum', 16, 1000]
['Platinum', 15, 1000]
['Platinum', 14, 1000]
['Platinum', 13, 1000]
['Platinum', 12, 1000]

因此您的算法确实有效，但由于您无法保留结果，因此它不会(完全)影响您的原始列表。