一维多尺寸装箱算法，浪费最少

Question

我正在尝试应用无限数量的一维装箱。

list = [1000, 1200, 2400, 1700, 3000, 500, 2800] # N number of data
bin = [3100, 2700, 2400] # N number of bins with all sizes available

我已经使用了 https://pypi.org/project/binpacking/ 库，但它不适用于多个尺寸的容器。我想要确切的库或代码或算法，可以通过使用最低的垃圾箱和最少的浪费来准确计算答案。我试图通过将其转换为一维来使用此 2D bin packing 库 https://github.com/secnot/rectpack 但它存在不计算最低浪费的漏洞。例如。如果只剩下两个值，400 和 500，那么算法应该只使用 2400 大小的 bin，相反，它采用行或列表中的下一个 bin。

Answer 1

我设法为这个问题创建了自己的逻辑。如您所见，我在代码中添加了很多注释，可以帮助您理解代码的不同部分。

import random
import binpacking

# DISTRIBUTES A DICTIONARY OF LENGTHS (KEY-VALUE = ID-LENGTH PAIR) TO A MINIMAL NUMBER IF BINS WHICH CAN HAVE DIFFERENT VOLUME.
def packing2dOptimizer(b, bin_bucket):

    # OPTIMIZED BINS WILL BE STORED HERE
    bin_list = []

    bin_bucket.append(0)
    bin_bucket.sort(reverse=True)

    # LIST OF DIFFERENCES BETWEEN BIN SIZES
    difference = [0]
    if len(bin_bucket) > 1:
        for index in range(1, len(bin_bucket)):
            difference.append(bin_bucket[0] - bin_bucket[index])

    # FIND THE EXACT BIN WIDTH AS PER USAGE OF PACKINGS
    def checkFinalSize(total):
        bin_width = 0
        for i in bin_bucket: 
            if total <= i: bin_width = i
            else: break
        return bin_width

    # PACK ALL THE VALUES IN BINS WITH MAXIMUM SIZE
    packer_list = binpacking.to_constant_volume(b,bin_bucket[0])

    # CREATE A DETAILED DATA OF BINPACKING
    counter = 0
    for packer in packer_list:
        bin_usage = sum(packer.values())
        bin_width = checkFinalSize(bin_usage)
        bin_waste = bin_width - bin_usage
        bin_data = {
            'bin_id': counter,
            'bin_width': bin_width,
            'bin_usage': bin_usage,
            'bin_waste': bin_waste,
            'pack_data': packer
        }
        counter += 1
        bin_list.append(bin_data)

    # PRINT THE LIST
    area_used = 0
    area_covered = 0
    area_waste = 0
    for i in bin_list: 
        print("Bin", i['bin_width'],":",i['pack_data'], i['bin_waste'])
        area_used += i['bin_width']
        area_covered += sum(i['pack_data'].values())
        area_waste +=  i['bin_waste']
    print()
    print("Area Used:", area_used)
    print("Area Covered:",  area_covered)
    print("Area Waste:",  area_waste)
    print()

    # TAKES TWO PACKED BINS AND THE AVAILABLE SIZES OF ALL BINS AS ARGUMENT
    def optimizer(small_bin, big_bin):
        dict1 = small_bin['pack_data']
        dict2 = big_bin['pack_data']

        # CREATE A NEW DICTIONARY OF DATA OF THE BOTH PACKED BINS
        new_dict = dict1.copy()
        new_dict.update(dict2)
        max_val = max(list(new_dict.values()))

        # FIND A SUITABLE BIN WITH LOWEST SIZE AND WASTAGE
        for size in bin_bucket:
            if size >= max_val:
                new_bins = binpacking.to_constant_volume(new_dict,size)    
                if len(new_bins) <= 2:
                    final_bins = new_bins

        # UPDATE BOTH PACKED BIN VALUES AND RETURNS
        big_bin['pack_data'] = final_bins[0]
        small_bin['pack_data'] = final_bins[1]
        return small_bin, big_bin

    # OPTIMIZE THE BINS TO MINIMIZE THE WASTE
    bin_bucket.sort(reverse=True)
    for small_bin in bin_list:
        if small_bin['bin_width'] == bin_bucket[-2] and small_bin['bin_waste'] > 0:
            for big_bin in bin_list:
                if big_bin['bin_width'] > small_bin['bin_width']:
                    pack_data = list(big_bin['pack_data'].values())
                    for length in pack_data:
                        if length <= small_bin['bin_waste']:
                            # CALL THE OPTIMIZER
                            small_bin, big_bin = optimizer(small_bin, big_bin)
                            
                            # UPDATE THE BIN DATA
                            bin_usage = sum(small_bin['pack_data'].values())
                            bin_width = checkFinalSize(bin_usage)
                            small_bin['bin_width'] = bin_width
                            small_bin['bin_usage'] = bin_usage
                            small_bin['bin_waste'] = bin_width - bin_usage

                            bin_usage = sum(big_bin['pack_data'].values())
                            bin_width = checkFinalSize(bin_usage)
                            big_bin['bin_width'] = bin_width
                            big_bin['bin_usage'] = bin_usage
                            big_bin['bin_waste'] = bin_width - bin_usage

                            break

    # SORT THE OPTIMIZED BINS BY BIN SIZE
    bin_list = sorted(bin_list, key = lambda i: i['bin_width'], reverse = True)

    # PRINT THE LIST
    area_used = 0
    area_covered = 0
    area_waste = 0
    for i in bin_list: 
        print("Bin", i['bin_width'],":",i['pack_data'], i['bin_waste'])
        area_used += i['bin_width']
        area_covered += sum(i['pack_data'].values())
        area_waste +=  i['bin_waste']
    print()
    print("Area Used:", area_used)
    print("Area Covered:",  area_covered)
    print("Area Waste:",  area_waste)

    return bin_list

def main():
    
    # LIST OF DATA THAT WILL BE SELECTED RANDOMLY
    random_data = [ i for i in range(100, 3200,100) ]

    # DIFFERENT SIZE OF VALUES WITH UNIQUE ID ASSOCIATED WITH IT
    b = {
        'a': random.choice(random_data), 
        'b': random.choice(random_data), 
        'c': random.choice(random_data), 
        'd': random.choice(random_data),
        'e': random.choice(random_data),
        'f': random.choice(random_data),
        'g': random.choice(random_data),
        'h': random.choice(random_data),
        'i': random.choice(random_data),
        'j': random.choice(random_data),
        'k': random.choice(random_data),
        'l': random.choice(random_data),
        'm': random.choice(random_data),
        'n': random.choice(random_data),
        'o': random.choice(random_data),
        'p': random.choice(random_data),
        'q': random.choice(random_data),
        'r': random.choice(random_data),
        's': random.choice(random_data),
        't': random.choice(random_data),
        'u': random.choice(random_data),
        'v': random.choice(random_data),
        'w': random.choice(random_data),
        'x': random.choice(random_data),
        'y': random.choice(random_data),
        'z': random.choice(random_data),
    }

    # LIST OF DIFFERENT SIZES OF BINS
    bin_bucket = [2400, 2700, 3100]

    bin_list = packing2dOptimizer(b, bin_bucket)

main()

一维多尺寸装箱算法，浪费最少

1D multiple sized bin packing algorithm with least waste

python

algorithm

optimization

bin-packing