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命令行中输入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

我觉得这里有一个更简单的方法。就是逐个查看可用的宝藏，尽可能多地获取你需要的东西。

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

Answer 2

主要的问题是你依赖于Python的引用传递来修改列表。最开始这样做是没问题的，但当你到达

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

时，Python会创建一个列表的副本，然后修改这个副本。所以，当你用完Diamonds后，你的原始列表并没有改变（你进入了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]

所以你的算法是有效的，但因为你没有办法保存结果，它并没有（完全）影响你的原始列表。