BPP问题及相关问题建模

大家好，欢迎来到IT知识分享网。

BPP问题介绍

概括：

BPP问题是指一维装箱问题，也简称装箱问题。将一组不同大小的物品装入一组容器中，每个容器的容量有限，目标是找到最优的装箱方案，使得所用容器数量最少。物品和箱子的体积都是一维的，通常表示为长度。

（1）物品集合：给定一组不同大小的待装物品，物品体积固定。

（2）箱子集合：一组可用的箱子，每个箱子的容量是固定的。

（3）装箱方案：将所有物品装入箱子的一种方案。

（4）目标函数：使用的箱子数量尽可能少。

（5）约束条件：每个物品必须完整放入一个箱子中，不能分割；每个箱子放入的总物品体积不能超过箱子容量。

建模：

符号介绍：

目标函数：

约束条件：

建模：

变尺寸装箱问题：

算法：

FF算法（First Fit Algorithm)

概括：

该算法按顺序逐个考虑物品，并尝试将物品放入第一个能够容纳它的容器中。

步骤：

（1）初始化：创建一个空箱子列表，每个箱子的容量为给定的最大容量。

（2）遍历物品：a.对每个物品，从左到右遍历现有的箱子列表；

                           b.对于每个箱子，检查物品是否可以放入当前箱子（即物品大小小于等于箱子剩余容量）；

                           c.如果找到可以放入该物品的箱子，则将物品放入，并更新箱子的剩余容量；

                           d.如果没有找到可以放入该物品的箱子，则创建一个新箱子，将物品放入新箱子中，并更新箱子列表。

（3）结果输出：所有物品都被放入箱子后，算法结束。箱子列表中的箱子数量即为所求的最小箱子数量。

优缺点：

较高的容器利用率，剩余空间少，但是容器分布不均衡。

NF算法（Next Fit Algorithm)

概括：

该算法按顺序逐个考虑物品，并尝试将物品放入当前打开的容器中。如果当前容器无法容纳该物品，则打开一个新的容器并将物品放入其中。

步骤：

（1）初始化：打开一个箱子，并将其设置为当前箱子，其容量为给定的最大容量。

（2）遍历物品：a.检查物品是否可以放入当前箱子（即物品大小小于等于箱子剩余容量）；

                           b.如果物品可以放入当前箱子，将该物品放入，并更新箱子的剩余容量；

                           c.如果物品无法放入当前箱子，则关闭当前箱子，打开一个新的容器，将物品放入新的箱子中，并将该箱子设置为当前箱子，更新箱子的剩余容量。

（3）结果输出：所有物品都被放入箱子后，算法结束。箱子列表中的箱子数量即为所求的最小箱子数量。

优缺点：

简单易实现，具有较高的效率。但是容器利用率较低。

BF算法（Best Fit Algorithm)

概括：

与FF算法和NF算法不同，BF算法在每次放置物品时尝试找到一个最合适的容器来容纳该物品，以最小化剩余空间。

步骤：

（1）初始化：创建一个空箱子列表，每个箱子的容量为给定的最大的容量。

（2）遍历物品：a.对每个物品，遍历现有的所有箱子，找出能够容纳该物品且剩余空间最小的箱子；

                           b.如果找到这样的箱子，则将物品放入该箱子，并更新箱子的剩余容量；

                           c.如果没有找到足够空间的箱子，则打开一个新箱子，将该物品放入新箱子中，并更新箱子列表。

（3）结果输出：所有物品都被放入箱子后，算法结束。箱子列表中的箱子数量即为所求的最小箱子数量。

优缺点：

该算法减少了使用箱子的数量，空间利用率较高。但是，每次遍历都需要搜索所有已打开的箱子，算法效率较低，计算成本高。

算法举例：

def get_min_boxes(things,box_weight): things=sorted(things,reverse=True)#将数据由大到小排序 print(things) m=len(things)-1;count=0 for i in range(len(things)): sum=0 print('{',end='') sum=things[i] print(things[i],' ',end='') while m>=0: j=m sum+=things[j] if sum>box_weight: count+=1 break print(things[j],'',end='') m-=1 if j==i: # count+=1 print('}') break print('}') print('最少需要使用',count,'个容积为',box_weight,'的箱子') if __name__=='__main__': things=[4,8,1,4,2,1] box_weight=10 # things=[3,15,14,19,13,4,10,4,20,3,1,7,13,8,18,18,20,5,9,8] # box_weight=20 get_min_boxes(things,box_weight)

一维装箱实例：

http://t.csdnimg.cn/8qVmK

二维装箱问题

组合优化问题，将一组不同大小的矩形物品放置到最少数量的矩形容器中。目标是以最小的空间浪费将所有物品放入容器，同时满足物品不重叠且完全位于容器内的约束。

物品和箱子都是二维的，通常表示为长和宽。

三维装箱问题

将一组不同大小的立方体物品放置到最少数量的立方体容器中。目标是以最小的空间浪费将所有物品放入容器，同时满足物品不重叠且完全位于容器内的约束。

应用：

物流与配送：确定最小数量的货车来运输一定量的货物，要考虑货车的载重限制，体积限制等等。

云计算资源优化：如何在云计算环境中分配虚拟机到物理服务器上，以最小化服务器的数量和能耗。

行李装载，仓库存储等等。