The minimum Bin Packing problem

img

给定条件 A finite set of objects X, where each object x in the set has a size s(x) and an integer b(bin size)

引入ChatGPT部分参考和理解：

import math

# 求解ceil(所有物品大小之和 ÷ bin大小)
def ceil_bin_size(sizes, bin_size): 
    total_size = sum(sizes) 
    return math.ceil(total_size / bin_size)

# 将3DM问题转化为MinBinPacking问题
def convert_3DM_to_MinBinPacking(X, Y, Z): 
    X_ = X + Y + Z 
    b = len(X) 
    objects = [] 
    for x in X: 
        for y in Y: 
            for z in Z: 
                objects.append((x, y, z)) 
                sizes = [1] * len(objects) 
                return X_, b, objects, sizes

# MinBinPacking问题的2-逼近算法
def min_bin_packing(objects, sizes, b): # 非递增排序  
 sorted_objects = sorted(objects, key=lambda o: sizes[objects.index(o)], reverse=True) # 创建空bin 
 bins = [[]] # 将每个物品放入第一个有足够空间的bin中或新建一个bin 
 for obj in sorted_objects:
     obj_size = sizes[objects.index(obj)] 
     bin_found = False for i in range(len(bins)): 
         if sum(sizes[objects.index(o)] for o in bins[i]) + obj_size <= b: 
             bins[i].append(obj) 
             bin_found = True 
             break 
             if not bin_found: 
                 bins.append([obj]) # 输出非空bin 
                 return [b for b in bins if len(b) > 0]

# 示例
# X = {'x1', 'x2'} Y = {'y1', 'y2', 'y3'} Z = {'z1', 'z2', 'z3'} X_, b, objects, sizes = convert_3DM_to_MinBinPacking(X, Y, Z) print(ceil_bin_size(sizes, b)) # output: 6 (ceil(18/2)) print(min_bin_packing(objects, sizes, b)) # output: [[('x2', 'y2', 'z3'), ('x2', 'y3', 'z2'), ('x1', 'y1', 'z2'), ('x1', 'y3', 'z1')], [('x2', 'y1', 'z1'), ('x1', 'y2', 'z3'), ('x2', 'y1', 'z2')]] (2 bins)

引用chatgpt部分指引作答：
运行结果如下：

img

python的示例代码如下:

import math

def bin_packing(X, b):
    n = len(X)
    s = sum(X)
    k = math.ceil(s/b)
    S = [[] for _ in range(k)]
    for x in sorted(X, reverse=True):
        min_bin = min(range(k), key=lambda i: sum(S[i]))
        S[min_bin].append(x)
    return S

这里，X 是对象大小的列表，b 是 bin 大小。 该函数返回一组集合 S 的列表，其中每个集合包含分配给单个容器的对象。

该算法的工作原理是首先使用问题陈述中提供的提示计算最佳箱数 k。 然后，它将每个对象分配给当前最轻的 bin，确保每个 bin 的总大小最多为 b。 按大小降序对对象进行排序可确保该算法是 2-approximation：在算法中的任何一点，最大的 k 个对象的总大小至少是最佳 bin 大小的两倍，因此至少有 k 个 bin 需要打包所有对象，算法最多产生 2k-1 个 bin。

要在示例输入上运行算法，您可以使用以下代码：

X = [2, 5, 4, 7, 1, 3, 8]
b = 10
S = bin_packing(X, b)
print(S)

输出结果：

[[8, 2], [7, 3], [5, 4, 1]]

表明最优包装至少需要 3 个 bin，算法产生 3 个 bin。

  • 以下回答由chatgpt基于相关博客总结生成:

    我可以给出一种解决最小装箱问题的贪心算法：

    1. 将所有物体按照大小从大到小排序。
    2. 初始化一个空箱子，将第一个物体放入箱子中。
    3. 对于剩余的每个物体，依次尝试将其放入当前箱子中。如果能够放下，则放入；如果放不下，则开启一个新的空箱子，并将该物体放入新箱子中。
    4. 重复步骤3直到所有物体都放入箱子中。

    具体实现代码如下：

    def pack_items(items, box_size):
    items = sorted(items, reverse=True)  # 按照大小从大到小排序
    boxes = [[]]  # 初始化一个空箱子列表
    for item in items:
        for box in boxes:
            if sum(box) + item <= box_size:  # 如果当前箱子可以放下该物体
                box.append(item)
                break
        else:  # 如果所有箱子都放不下，则开启一个新箱子
            boxes.append([item])
    return boxes

    例如，如果有物体集合X=[3,4,5,6,7,8,9]，箱子大小为10，则该函数的输出为[[9, 1], [8, 2], [7, 3], [6, 4], [5]]，即需要5个箱子才能将所有物体放入。

该回答引用ChatGPT
最小装箱问题 (Minimum Bin Packing problem) 是一种经典的组合优化问题，目的是将一组物品装入尽可能少的容量相同的容器(称为 bin)，要求物品不能被分割，且每个物品大小不同，每个容器容量相同。

传统的最小装箱问题是 NP-hard 问题，可以使用一些近似算法来解决。下面是一个贪心算法的例子：


// 输入：物品数组 items，容器大小 capacity
// 输出：所需容器数 count，以及每个容器内所装物品的编号数组 bins
int binPacking(int[] items, int capacity, List<List<Integer>> bins) {
    bins.clear();   // 清空容器数组
    Arrays.sort(items); // 按物品大小从小到大排序
    int count = 0;
    for (int i = items.length - 1; i >= 0; i--) {
        int item = items[i];
        boolean ok = false;
        for (List<Integer> bin : bins) {
            if (bin.size() > 0 && bin.get(bin.size() - 1) + item <= capacity) {
                bin.add(item);
                ok = true;
                break;
            }
        }
        if (!ok) {
            List<Integer> bin = new ArrayList<>();
            bin.add(item);
            bins.add(bin);
            count++;
        }
    }
    return count;
}


上述算法从大到小依次考虑每个物品，对于每个物品，遍历所有容器，找到第一个容器能够容纳该物品，则将该物品加入该容器中，否则新开一个容器来装该物品。

这个算法的时间复杂度为 $O(n^2)$，其中 $n$ 是物品数目。如果想优化时间复杂度，可以使用一些更高效的近似算法，比如 First Fit Decreasing (FFD) 或 Best Fit Decreasing (BFD)。

以下答案由GPT-3.5大模型与博主波罗歌共同编写：
Minimum Bin Packing Problem（最小箱装问题）是NP难问题之一，可以使用启发式算法求解。

基本的贪心算法是先将物品按照大小从大到小排序，然后依次将物品放入当前可用空间最小的箱子中。具体实现可以使用优先队列（最小堆）来维护可用空间最小的箱子。

以下是基于贪心算法的Python代码实现：

import heapq

def bin_packing(X, b):
    # 按照大小从大到小排序
    X = sorted(X, reverse=True)
    # 初始化箱子，将首个物品放入第一个箱子
    bins = [X[0]]
    # 记录每个箱子的剩余空间
    spaces = [b - X[0]]
    # 遍历物品，依次放入箱子中
    for x in X[1:]:
        # 在空余空间中寻找最小的箱子
        min_space_idx = heapq.nsmallest(1, range(len(spaces)), key=spaces.__getitem__)[0]
        # 如果该箱子能够容纳当前物品，则直接放入
        if spaces[min_space_idx] >= x:
            spaces[min_space_idx] -= x
            bins[min_space_idx].append(x)
        # 如果该箱子容纳不下当前物品，则新开一个箱子
        else:
            bins.append([x])
            spaces.append(b - x)
    return bins

# 示例
X = [10, 8, 7, 5, 2]
b = 10
bins = bin_packing(X, b)
print(bins)  # [[10], [8, 2], [7, 5]]

该代码的时间复杂度为O(nlogn)，其中n是物品的数量。注意，该算法得到的是一个近似最优解，不一定是最优解。如果需要获取最优解，可以使用穷举法或者动态规划等方法，但是其时间复杂度会更高。
如果我的回答解决了您的问题，请采纳！