如何将多个矩形打包为 2d 盒子俄罗斯方块样式

我有许多不同宽度和高度的矩形。我有一个更大的矩形平台来放置它们。我想将它们包装在平台的一侧，以便它们在纵向 (X) 尺寸上展开，但将横向 (Y) 尺寸保持在最小限度。就是把它们像俄罗斯方块游戏一样放置。不能有重叠，但可以有间隙。有没有算法可以做到这一点？

听起来像是一个变体箱式包装 http://en.wikipedia.org/wiki/Bin_packing_problem:

在计算复杂性理论中， 装箱问题是 组合 NP 难题。在里面， 不同体积的物体必须 打包到有限数量的 bin 中 容量V以最小化的方式 使用的垃圾箱数量。

这个有很多变体 问题，例如 2D 堆积、线性 包装、按重量包装、按重量包装 成本等。他们有很多 应用程序，例如填写 集装箱、载重卡车 容量，创建文件备份 可移动媒体和技术映射 在 FPGA 中实现定制 硬件。

来自同一页面的有关可能解决方案的引用：

由于它是 NP 困难的，因此最有效的已知算法使用 启发式方法来实现结果 虽然在大多数情况下都很好， 可能不是最佳解决方案。为了 例如，第一个拟合算法 提供了快速但通常不是最佳的 解决方案，涉及放置每个项目 放入第一个垃圾箱中 合身。需要 θ(n log n) 时间， 其中 n 是元素的数量 打包。算法可作 通过第一次排序更有效 将元素列表变为递减 顺序（有时称为 首次拟合递减算法）， 尽管这并不能保证 最佳解决方案，以及更长的列表 可能会增加运行时间 算法。

我建议您点击该维基百科页面上的一些链接。另外，通过谷歌搜索“装箱算法”，您可能会找到很多相关信息。