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

私はその最大の機能に問題に実行してM、ここに私の出力です：

['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 

私はそれは最大に空の文字列を落とすと思うが、私はなぜ、最後の要素が使用された後にループを終了する必要があります理解していない。誰か助けてくれますか？

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] 

削除を持っています合計の前にmydictのすべての要素が制限に達するので、空のdictでkeywithmaxvalを呼び出すことになります。それによって例外が発生します。

一つの可能​​性のある修正は、ループに "not empty"チェックを追加することです。

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

ところで、 PDBはあなたの友人です。