Python中的贪婪算法

Question

我想让c(aList，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)]

我试图让掠夺(aList，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中输入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的pass by引用来修改列表。一开始效果很好，但当你到达

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]

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

Answer 2

我认为这是一个更简单的方法。只需迭代一遍可用的宝藏，并尽可能多地从每个宝藏中获取。

def demo():
    units_to_plunder = 10
    treasure = new_treasure_pile()
    plundered_units = plunder_units(treasure, units_to_plunder)
    print treasure
    print plundered_units

    units_to_plunder = 1000
    treasure = new_treasure_pile()
    plundered_units = plunder_units(treasure, units_to_plunder)
    print treasure
    print plundered_units



def plunder_units(treasure, total_plunder_units):
    treasure_sorted = list(sorted(treasure, key=lambda t: t[2], reverse=True))
    plundered = list()
    for treasure_type in treasure_sorted:
        # stop condition when desired units taken
        if total_plunder_units <= 0:
            break
        t_units_to_take = min(total_plunder_units, treasure_type[1])
        # update the 3 moving parts
        treasure_type[1] -= t_units_to_take
        plundered.append([treasure_type[0], t_units_to_take, treasure_type[2]])
        total_plunder_units -= t_units_to_take
    return plundered


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


if __name__ == '__main__':
    demo()

c=10的输出(我认为正如您所期望的那样)

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

c=1000的输出(全部接受)

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