algorithm - 最佳二维装箱

Question

给定一组不同大小的矩形（项目）和一组相同大小的矩形（箱），将物品放入尽可能少的箱中。

我知道打包垃圾箱的一千种方法，但我想知道，如果物品的数量适当地小而且尺寸可能是整数，有没有办法总是以最佳方式打包物品？有人知道最佳矩形箱包装的策略或算法吗？

标签： algorithmoptimizationgeometryknapsack-problembin-packing

Answer 1

看看Lodi 等人的调查。关于二维装箱问题，其中有一节是关于精确算法的。对于极少数项目，您可能能够使用整数规划模型解决问题，对于较大的项目，您可能需要定制的树搜索或分支定界算法。一个例子是Pisinger & Sigurd的文章，它使用 Dantzig-Wolfe 分解并依赖约束规划来打包单个箱，并且能够解决大约 100 个项目的问题。