如何在2d盒子俄罗斯方块样式中包装多个矩形

Question

我有许多不同宽度和高度的矩形。我有一个更大的矩形平台来放置它们。我想将它们包装在平台的一侧，以便它们在纵向（X）维度上展开，但将宽度（Y）维度保持为最小。那就是把它们放置成一个俄罗斯方块游戏。不可能有重叠，但可能会有差距。有没有算法可以做到这一点？

Answer 1

听起来像是Bin Packing变化：

在计算复杂性理论， 的装箱问题是一个 组合NP难问题。其中， 不同体积的物体必须以 打包成有限数量的容量为V的容器，以最小化所使用的容器数量的 数量。

这个 问题有很多变化，比如2D包装，线性包装，重量包装，包装成本等等。他们有很多 应用，如填充 容器，具有重量 容量装载卡车，在 可移动媒体和FPGA实现定制 硬件的技术映射 创建文件备份。

在同一页面引述有关可能的解决方案：

既然是NP难的，最有效的已知算法使用 启发式完成结果 这虽然在大多数情况下非常好， 可能不是最佳解决方案。例如，第一个拟合算法 提供了一个快速但通常不是最佳的解决方案，涉及将每个项目 放置到其拟合的第一个箱中。它需要Θ（n log n）时间， 其中n是要打包的要素数 。该算法可以由 有效得多通过第一分拣 元素列表成递减 顺序（有时也被称为 第一配合减少算法）， 虽然这并不能保证一个 最优解，并且对于较长的列表 可能会增加算法的运行时间。

我建议您按照维基百科页面的一些链接。另外，通过谷歌搜索“bin包装算法”，您可能会发现很多相关信息。

Answer 2

这被称为二维条形包装，并已由Martello进行过工作。如果你在谷歌搜索他们的论文，他们的算法应该很容易实现。一种方法是使用分支和界限来解决您的问题。首先计算一个贪婪的解决方案，以获得包装所需的最大高度。

然后，您的算法应该先找到一组有希望的x坐标，然后找到矩形的y坐标。换句话说，对于每个矩形，都可以分配所有可能的x坐标。在任何时间点，您都可以保留占据任何特定x坐标的总高度的总和（这称为累积约束），并修剪高度是否超过您的全局最大高度。对于已经分配了所有矩形的x坐标的每个完整x坐标解法，现在可以尝试找到有效的y坐标。你可以用相同的方法做到这一点，对于每个矩形，在不同的可能的y坐标上分支，当你知道两个矩形相互重叠时修剪。在树的底部，您可以找到矩形的x和y坐标，您可以在此处计算所需的高度，并更新最大上限。

如果您在更新上限时保存了当前的解决方案，那么当算法终止时，您将获得最佳解决方案。