Python

Question

我正在尝试在 python 中根据下面的数据集实现一个贪婪的背包算法。输出应该是一个列表列表，它遵守限制集。例如下面的数据集输出应该是：

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

代码：

data = {
        'A': 5,
        'B': 10,
        'C': 11,
        'D': 7,
        'E': 2,
        'Z': 4,
        'F': 3
}

def greedy_algo(mystuff, limit=30):

    # Copy the dictionary to work on duplicate
    copy_stuff = dict(mystuff)
    # Initialize an output list
    outlist = []

    def keywithmaxval(d):
     """ a) create a list of the dict's keys and values; 
     b) return the key with the max value"""  
        v=list(d.values())
        k=list(d.keys())
        return k[v.index(max(v))]


    def greedy_grab(mydict):
        result = []
        total = 0
        while total <= limit:
            maxkey=keywithmaxval(mydict)
            result.append(maxkey)
            total += mydict[maxkey]
            del mydict[maxkey]
        return result

    def update_dict(mydict, mylist):
        for i in mylist:
            del mydict[i]
        return mydict     

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


    return outlist


print (greedy_algo(data, limit=30))

我运行遇到了那个 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。然后循环

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

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

一个可能的修复方法是将 "not empty" 检查添加到循环中。

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

顺便说一句。 PDB 是你的朋友。

Python - 带有字典输入的贪婪背包

Python - Greedy Knapsack with Dictionary input

dictionary

knapsack-problem