Python - Greedy Knapsack with Dictionary input

Question

i am trying to implement a greedy knapsack algorithm in python given the data set below. The output is supposed to be a list of lists, that observes the limit set. In example with the dataset below the output should be :

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

Code:

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

I m running into a problem with that max function, here's my output :

['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 guess it drops an empty string into max, but i dont understand why, the while should terminate the loop after the last element has been used. Can someone help me?

Answer 1

Well, the first execution of greedy_grab is more or less fine (the result is greater than the limit because you check the limit after inserting the item, but it doesn't raise any exception).

But when it finishes, the loop

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

executes again the function, but this time the "copy_stuff" dict only have F, E and Z. Then the loop

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

Deletes all the elements in mydict before total reaches the limit, so you end up calling keywithmaxval with an empty dict. That raises the exception.

One posible fix is adding the "not empty" check to the loop.

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

By the way. PDB is your friend.