打包

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

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

背包问题

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

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

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

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

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

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

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

装箱问题

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

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

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

  • 装箱：您有 20 辆卡车（足以容纳所有物品），并且希望使用最少的卡车来装运所有物品。

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