[FIXED] Python 3: IndexError: list index out of range while doing Knapsack Problem

Issue

I am currently self-learning python for a career change. While doing some exercises about 'list', I encountered IndexError: list index out of range.

So, I am trying to build a function, that determines which product should be placed on my store's shelves. But, I also put constraints.

1. The shelve has a max capacity of 200
2. small-sized items should be placed first
3. if two or more items have the same size, the item with the highest price should be placed first

As an input for the function, I have a list of tuples "dairy_items", denoted as [(id, size, price)].

This is my code:

capacity=200

dairy_items=[('p1', 10, 3), ('p2', 13, 5),
            ('p3', 15, 2), ('p4', 26, 2),
            ('p5', 18, 6), ('p6', 25, 3),
            ('p7', 20, 4), ('p8', 10, 5),
            ('p9', 15, 4), ('p10', 12, 7),
            ('p11', 19, 3), ('p12', 27, 6),
            ('p13', 16, 4), ('p14', 23, 5),
            ('p15', 14, 2), ('p16', 23, 5),
            ('p17', 12, 7), ('p18', 11, 3),
            ('p19', 16, 5), ('p20', 11, 4)]

def shelving(dairy_items):
    #first: sort the list of tuples based on size: low-to-big
    items = sorted(dairy_items, key=lambda x: x[1], reverse=False)
    #second: iterate the sorted list of tuples.
    #agorithm: retrieve the first 2 elements of the sorted list 
            #then compare those two elements by applying rules/conditions as stated
                #the 'winning' element is placed to 'result' and this element is removed from 'items'. Also 'temp' list is resetted
                #do again untill shelves cannot be added anymore (capacity full and do not exceeds limit) 
    result = []
    total_price = []
    temp_capacity = []
    temp = items[:2]
    while sum(temp_capacity) < capacity:
        #add conditions: (low first) and (if size the same, highest price first)
        if (temp[0][1] == temp[1][1]) and (temp[0][2] > temp[1][2]):
            temp_capacity.append(temp[0][1])
            result.append(temp.pop(0))
            items.pop(0)
            temp.clear()
            temp = items[:2]
            total_price.append(temp[0][2])
        elif ((temp[0][1] == temp[1][1])) and (temp[0][2] < temp[1][2]):
            temp_capacity.append(temp[1][1])
            result.append(temp.pop())
            items.pop()
            temp.clear()
            temp = items[:2]
            total_price.append(temp[1][2])
        else:
            temp_capacity.append(temp[0][1])
            result.append(temp.pop(0))
            items.pop(0)
            temp.clear()
            temp = items[:2]
            total_price.append(temp[0][2])
    result = result.append(temp_capacity)
    #return a tuple with three elements: ([list of product ID to be placed in order], total occupied capacity of shelves, total prices)
    return result 

c:\Users\abc\downloads\listexercise.py in <module>
----> 1 print(shelving(dairy_items))

c:\Users\abc\downloads\listexercise.py in shelving(dairy_items)
     28     while sum(temp_capacity) < capacity:
     29 
---> 30         if (temp[0][1] == temp[1][1]) and (temp[0][2] > temp[1][2]):
     31             temp_capacity.append(temp[0][1])
     32             result.append(temp2.pop(0))

IndexError: list index out of range

EDIT:

This is the expected result:

#Result should be True
print(shelving(dairy_items) == (['p8', 'p1', 'p20', 'p18', 'p10', 'p17', 'p2', 'p15', 'p9', 'p3', 'p19', 'p13', 'p5', 'p11'], 192, 60))

Solution

The IndexError occured because, you had tried to append the 2nd element after popping it from temp because, after popping it out, there will be only one element in temp which can indexed with 0.

Also I noticed a few more bugs which could hinder your program from giving the correct output and rectified them.

The following code will work efficiently...

from time import time

start = time()

capacity = 200

dairy_items = [('p1', 10, 3), ('p2', 13, 5),
            ('p3', 15, 2), ('p4', 26, 2),
            ('p5', 18, 6), ('p6', 25, 3),
            ('p7', 20, 4), ('p8', 10, 5),
            ('p9', 15, 4), ('p10', 12, 7),
            ('p11', 19, 3), ('p12', 27, 6),
            ('p13', 16, 4), ('p14', 23, 5),
            ('p15', 14, 2), ('p16', 23, 5),
            ('p17', 12, 7), ('p18', 11, 3),
            ('p19', 16, 5), ('p20', 11, 4)]

def shelving(dairy_items):
    items = sorted(dairy_items, key=lambda x: x[1])
    result = ([],)
    total_price, temp_capacity = 0, 0

    while (temp_capacity+items[0][1]) < capacity:
        temp = items[:2]

        if temp[0][1] == temp[1][1]:
            if temp[0][2] > temp[1][2]:
                temp_capacity += temp[0][1]
                result[0].append(temp[0][0])
                total_price += temp[0][2]
                items.pop(0)
            elif temp[0][2] < temp[1][2]:
                temp_capacity += temp[1][1]
                result[0].append(temp[1][0])
                total_price += temp[1][2]
                items.pop(items.index(temp[1]))
            else:
                temp_capacity += temp[0][1]
                result[0].append(temp[0][0])
                total_price += temp[0][2]
                items.pop(0)
        else:
            temp_capacity += temp[0][1]
            result[0].append(temp[0][0])
            total_price += temp[0][2]
            items.pop(0)

    result += (temp_capacity, total_price)
    return result

a = shelving(dairy_items)

end = time()

print(a)

print(f"\nTime Taken : {end-start} secs")

Output:-

(['p8', 'p1', 'p20', 'p18', 'p10', 'p17', 'p2', 'p15', 'p9', 'p3', 'p19', 'p13', 'p5', 'p11'], 192, 60)

Time Taken : 3.123283386230469e-05 secs

Answered By - MK14