Python贪心背包，字典inpu

Question

我试图在python中实现一个贪婪的背包算法，给出下面的数据集。输出应该是一个列表列表，它遵守了设置的限制。在下面的数据集示例中，输出应为：

out = [[C, B, D, A], [Z, F, E]]

代码：

^{pr2}$

我在max函数上遇到问题，输出如下：

['C']
['C', 'B']
['C', 'B', 'D']
['C', 'B', 'D', 'A']
['Z']
['Z', 'F']
['Z', 'F', 'E']
Traceback (most recent call last):
  File "gre.py", line 72, in <module>
    greedy_algo(data, limit=30)
  File "gre.py", line 63, in greedy_algo
    outlist.append(greedy_grab(copy_stuff))
  File "gre.py", line 40, in greedy_grab
    maxkey=keywithmaxval(mydict)
  File "gre.py", line 28, in keywithmaxval
    return k[v.index(max(v))]
 ValueError: max() arg is an empty sequence

我想它会将一个空字符串放入max中，但是我不明白为什么while应该在最后一个元素被使用之后终止循环。有人能帮我吗？在

Answer 1

好吧，greedy_grab的第一次执行或多或少是好的（结果大于限制，因为您在插入项之后检查限制，但它不会引发任何异常）。在

但当它结束时，循环

while len(copy_stuff) > 0:
    outlist.append(greedy_grab(copy_stuff))

再次执行函数，但这次“copy_stuff”dict只有F、E和Z。然后是循环

^{pr2}$

在total达到限制之前删除mydict中的所有元素，因此您最终使用空dict调用keywithmaxval。这会引发异常。在

一个可能的修复方法是将“notempty”检查添加到循环中。在

while total <= limit and len(mydict) > 0:
        maxkey=keywithmaxval(mydict)
        result.append(maxkey)
        total += mydict[maxkey]
        del mydict[maxkey]

顺便说一下。PDB是你的朋友。在