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 

我猜猜它將一個空字符串放入最大值，但我不明白爲什麼，在最後一個元素被使用後，while應該終止循環。有人能幫我嗎？

Answer 1

那麼，greedy_grab的第一次執行是或多或少（結果大於限制，因爲您在插入項目後檢查限制，但不會引發任何異常）。

但是，當它完成，循環

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

再次執行的功能，但是這一次的 「copy_stuff」 字典只有F，E和Z.隨後環路

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

刪除mydict之前的所有元素都達到了限制，所以你最終會用空dict調用keywithmaxval。這引起了例外。

一個可行的方法是在循環中添加「不空」檢查。

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

順便說一句。 PDB是你的朋友。