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

Я бегу в проблему с тем, что максимальная функция, вот мой выход:

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

I угадайте, что он пустил пустую строку в max, но я не понимаю, почему 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 до полного достигнут предела, поэтому вы в конечном итоге вызываете keywithmaxval с пустым dict. Это вызывает исключение.

Одно возможное исправление добавляет к петле «непустую» проверку.

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

Кстати. PDB - ваш друг.