打包

打包问题的目标是找到将一组给定大小的项打包到具有固定packing的容器中的最佳方式。packing典型应用是高效地将箱子加载到货车上。 通常,由于容量限制,无法打包所有商品。在这种情况下,问题是找出总大小不超过最大可容纳在容器中的项的子集。

打包问题有多种类型。其中最重要的两个是“背包问题”和“装箱问题”。

背包问题

在简单的背包问题中,只有一个容器(背包)。这些项具有和尺寸,目标是打包具有最高总价值的部分项。

对于值等于大小的特殊情况,目标是使打包商品的总大小最大化。

OR-Tools 在其算法库中为背包问题提供了多种求解器。

此外,背包问题还有更普通的版本。以下是几个示例:

  • 多维背包问题,此类问题是指物品有多个物理数量(例如重量和体积),背包对每个数量都有容量。这里,术语不一定是指高度、长度和宽度的常规空间维度。但是,一些问题可能涉及空间维度,例如,寻找将矩形箱打包到矩形存储箱中的最佳方法。

  • 多个背包问题,此类问题涉及多个背包,目标是使所有背包中已打包的物品的总价值最大化。

请注意,您可能是针对单个背包的多维问题,也可能是只有一个维度的多维背包问题。

装箱问题

最广为人知的打包问题之一是装箱,即装箱时有多个容量相同的容器(称为装箱)。bin-packingbin-packing与多背包问题不同,箱子的数量并非固定的。相反,目标是找到容纳所有项的最小数量的分箱。

下面这个简单的示例说明了多背包问题和装箱问题之间的区别。假设一家公司有货运卡车,每辆卡车的承重能力为 18,000 磅,需要运送 130,000 磅的商品。

  • 多个背包:您有五辆卡车,您想加载其中最重的物品。

  • 装箱:您有 20 辆卡车(足以容纳所有物品),并且希望使用最少的卡车来装运所有物品。

以下各部分介绍如何使用 OR-Tools 解决各种类型的打包问题,从背包问题开始。