algorithm - 什么算法可用于以相当优化的方式将不同大小的矩形打包成尽可能小的矩形？

Question

我有一堆矩形物体，我需要将它们打包到尽可能小的空间中(这个空间的尺寸应该是 2 的幂)。

我知道各种打包算法可以将物品尽可能好地打包到给定的空间中，但是在这种情况下，我需要该算法来计算出该空间应该有多大。

例如说我有以下矩形

128*32

128*64

64*32

64*32

它们可以打包成一个 128*128 的空间

_________________
|128*32 |
|________________|
|128*64 |
| |
| |
|________________|
|64*32 |64*32 |
|_______|________|

但是，如果还有一个 160*32 和一个 64*64 的，则需要 256*128 的空间

________________________________
|128*32 |64*64 |64*32 |
|________________| |_______|
|128*64 | |64*32 |
| |_______|_______|
| | |
|________________|___ |
|160*32 | |
|__________|___________|

有哪些算法可以打包一堆矩形并确定容器所需的大小(2 的幂，并且在每个维度的给定最大大小内)？

Answer 1

快速而肮脏的第一遍解决方案总是一个很好的开始，如果没有别的，作为比较。

贪婪的放置从大到小。

将剩余的最大矩形放入您的打包区域。如果它不能放在任何地方，请将其放置在尽可能少地扩展包装区域的地方。重复直到完成最小的矩形。

它并不完美，但它很容易并且是一个很好的基线。它仍然可以完美地打包您的原始示例，并为您提供第二个等效的答案。