Python中的贪婪算法

Question

我想要掠夺中的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

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

^{pr2}$

我试图让掠夺者（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]]

而且当我在pythonshell中输入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（'capacity'）是0。2个钻石+8个铂=10（这是我的c）。在

Answer 1

主要问题是依赖Python的列表传递引用来修改列表。 一开始很好，但是当你达到

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

Python创建列表的副本，并继续修改该副本。因此，在钻石用完后，原始列表保持不变（点击else部分）。在

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

^{pr2}$

如果在函数中添加print alist[-1]语句，则可以更清楚地看到它。在

^{3}$

所以你的算法是有效的，但是你没有办法保持结果，它不会（完全）影响你原来的列表。在

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的输出（我想如你所料）

^{pr2}$

c=1000的输出（全部取）

^{3}$