Best Fit Algorithm Help

Question

def BestFit():

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)

I want to alter this part of the code:

for box in boxes:

l = box[0]

w = box[1]

area = l * w

for i in range(len(area_remaining_in_bins)):

for i in range(len(area_remaining_in_bins)):

minimum = area_remaining_in_bins[i]

if (area <= area_remaining_in_bins[i]) and (area_remaining_in_bins[i] - area <= minimum):

area_remaining_in_bins[i] = area_remaining_in_bins[i] - area

minimum = area_remaining_in_bins[i]

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

break

I want it to place the boxes, not in previous boxes that need to be filled, but more specifically, to be placed into the box that will result in the less area left overall (tightest spot).

I'm don't necessarily know how to translate it into code, where the area left will be less than just doing the first-fit algorithm.

Answer 1

If I understand you correctly, then for each box you want to iterate over all the bins,

find the one (minimum_i below) that would result in the tightest fit, and then use it.

Below is a possible code. I did not make sure that it is valid Python

for box in boxes:

l = box[0]

w = box[1]

area = l * w

# minimum_i is the index of the bin that

# would have the tightest fit.

# Initially minimum_i is set to a negative value (invalid index)

# indicating that initially no bin has been found that

# can even fit the box.

# minimum is the actual amount of area that would be left if

# the minimum_i were chosen.

# It is initially "infinite" so that

# the first acceptable bin will be chosen.

minimum = sys.maxsize

minimum_i = -1

for i in range(len(area_remaining_in_bins)):

# remaining is the amount of space left over

# if bin i were chosen.

remaining = area_remaining_in_bins[i] - area

# To be acceptable, bin i must be big enough,

# i.e. remaining >= 0.

# For bin i to be chosen as the new candidate

# it must be an improvement.

if (remaining >= 0) and (remaining < minimum):

minimum = remaining

minimum_i = i

if (minimum_i < 0):

# No existing bin is big enough for box.

# I am not sure what you do for that.

# I do not understand why you have "i += 1" in the original code

else:

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

break