CODEWITHSUNDEEP
pythonalgorithmbin-packing
Brittney P
Brittney P

Reputation: 31

First Fit Bin Packing Algorithm

I'm trying to create a First Fit Algorithm. The approach I'm taking is creating a list of empty lists, which are representative of the bins, where they will then be filled by certain area values that add up to the bin area. I want that to be continued until most of the areas can be filled.

This is where my problem arises:

lists.append([])
for i in lists:
    for box in boxes:
        l = box[0]
        w = box[1]
        area = l * w
        if area <= bin_area:
            bin_area = bin_area - area
            lists[0].append(area)
        else:
            bin_area = 15
            if area <= bin_area:
                bin_area = bin_area - area
                lists[1].append(area)
                # Here I want to then create a new empty list 
                # where I can add more values that add up to the bin value.

So at the end of the above code I want to create a new empty list where I can add more values that add up to the bin value.

I tried, by guessing, lists[ i ].append([area]), but the index has to be integer.

How do I accomplish this?

Also, here is my full code:

def FirstFitAlg():
    box1 = (3,2)
    box2 = (1,4)
    box3 = (2,1)
    box4 = (4,3)
    box5 = (1,2)
    boxes = [box1,box2,box3,box4,box5]
    num_of_boxes = len(boxes)
    bin_area = 15
    n_bin = 0
    lists = []
    lists.append([])
    lists.append([])
    #for i in lists:
    for box in boxes:
        l = box[0]
        w = box[1]
        area = l * w
        if area <= bin_area:
            bin_area = bin_area - area
            lists[0].append(area)
        else:
            bin_area = 15
            if area <= bin_area:
                bin_area = bin_area - area
                lists[1].append(area)
                # Here I want to then create a new empty list 
                # where I can add more values that add up to the bin value. 

    print(lists)
    for i in lists:
        if len(i) >= 1:
            n_bin += 1

    print(n_bin)
    efficiency = (n_bin/num_of_boxes) * 100
    print(efficiency)

Upvotes: 1

Views: 1786

Answers (1)

trincot
trincot

Reputation: 350137

Keep the printing out of your function, and pass it the box information as argument. That way it is more generic.

Here is how it could work:

def firstFitAlg(boxes, bin_area):
    bins = []
    current_bin_area = 0
    total_occupied = 0
    for box in boxes:
        l, w = box
        area = l * w
        total_occupied += area
        if area > current_bin_area:  # Overflow. Need new bin
            current_bin = []  # Create new bin
            current_bin_area = bin_area  # All space is available in it
            bins.append(current_bin)  # This bin is part of the solution
        current_bin.append(box)  # Add box in this bin
        current_bin_area -= area  # and reduce the available space in it

    return bins, total_occupied


boxes = [(3,2),(1,4),(2,1),(4,3),(1,2)]
bin_area = 15
bins, total_occupied = firstFitAlg(boxes, bin_area)

print(bins)
print(f"Bumber of bins: {len(bins)}")
efficiency = (total_occupied/(bin_area * len(bins))) * 100
print(f"Efficiency: {efficiency}")

Upvotes: 2

Related Questions