Next Fit Algorithm Help

Question

def NextFit():

boxes = readCSV()

num_of_boxes = len(boxes)

bin_area = 40

n_bin = 0

area_remaining_in_bins = []

lists = []

for x in range(num_of_boxes):

area_remaining_in_bins.append(bin_area)

lists.append([])

print(boxes)

#for i in lists:

for box in boxes:

l = box[0]

w = box[1]

area = l * w

for i in range(len(area_remaining_in_bins)):

if area <= area_remaining_in_bins[i]:

area_remaining_in_bins[i] = area_remaining_in_bins[i] - area

lists[i].append((l,w))

break

else:

i+=1

for i in lists[:]:

if len(i) == 0:

lists.remove(i)

for j in area_remaining_in_bins[:]:

if j == 40:

area_remaining_in_bins.remove(j)

num_of_boxes_packed = []

b = []

for i in lists:

if len(i) >= 1:

n_bin += 1

na = len(i)

num_of_boxes_packed.append(na)

This is my code, it is the first-fit algorithm. I'm trying to change this part of the algorithm:

for box in boxes:

l = box[0]

w = box[1]

area = l * w

for i in range(len(area_remaining_in_bins)):

if area <= area_remaining_in_bins[i]:

area_remaining_in_bins[i] = area_remaining_in_bins[i] - area

lists[i].append((l,w))

break

else:

i+=1

The tuples will be inserted into the bin that it fits into. I want it to fit into the bin until the area is greater, where it will then create a new bin and won't fill in existing bins. I tried adding the else statement, but it does not work.

Just an example of what it does now:

Let's say the bin_area = 10

boxes = [(1,2),(2,2),(3,3)(1,1))]

lists = [ [(1,2), (2,2), (1,1)] , [(3,3)] ]

This is what I want it to do:

boxes = [(1,2),(2,2),(3,3)(1,1))]

lists = [ [(1,2),(2,2)], [(3,3), (1,1)]

So I want it to basically abandon the previous bin when it comes across a box that has an area greater than the remaining area.

If you could provide some guidance or hints that would be helpful, that would be greatly appreciated! Thank you so much!

Answer 1

The problem is your for loop, starts at 0, which is going to be the very beginning of the bin spaces. In order to fix it, you can use range with 2 arguments such as "range(start, stop)" which will generate an iterable from start to stop - 1.

Another problem is, unlike in c++, variables in for loops aren't actually the same variable throughout the whole loop. When the loop continues to the next iteration, the previous "i" is completely abandoned and it becomes the new i from the range function.