首次适配装箱算法

Question

我正在尝试创建一个首次拟合算法。我采用的方法是创建一个空列表列表，这些空列表代表垃圾箱，然后它们将由某些区域值填充，这些区域值加起来就是垃圾箱区域。我希望继续下去，直到大部分区域都可以被填满。

这是我的问题所在：

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.

所以在上面代码的末尾，我想创建一个新的空列表，我可以在其中添加更多值，这些值加起来就是 bin 值。

我试过，通过猜测，lists[ i ].append([area])，但索引必须是整数。

我该如何完成？

此外，这是我的完整代码：

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)

Answer 1

将打印保留在函数之外，并将框信息作为参数传递给它。这样它就更通用了。

这是它的工作原理：

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

首次适配装箱算法

First Fit Bin Packing Algorithm

python

algorithm

bin-packing