可以用什么算法将不同大小的矩形以相当理想的方式打包成尽可能小的矩形？

参见ARC项目上的这个页面对解决方案的调查，在实现复杂性/时间和优化性之间有一个权衡，但有广泛的算法可供选择。 这里'是算法的摘录。

1. 第一拟合递减高度（FFDH）算法。 FFDH将下一个物品R（以非递增的高度）打包到R适合的第一层。 如果没有层可以容纳R，则创建一个新的层。 FFDH的时间复杂度。 O(n·log n). 近似比。 FFDH(I)<=(17/10)·OPT(I)+1; 17/10的渐近边界很紧。

2. 下一步拟合递减高度（NFDH）算法 如果R适合，则NFDH将下一个物品R（以非递增高度）打包到当前层。 否则，当前层级将被"关闭&quot。 并创建一个新的关卡。 时间复杂度。 O(n·log n). 近似率：NFDH(I) &lt。 NFDH(I) <=2·OPT(I)+1。 2的渐进边界很紧。

3. 最佳拟合递减高度（BFDH）算法 BFDH将下一个项目R（以非递增的高度）打包到可以容纳R的层上，剩余的水平空间是最小的。 如果没有层可以容纳R，则创建一个新的层。

4. 左下角（BL）算法 BL首先按非递增的宽度排列物品。 BL 将下一个物品打包到最接近底部的位置，然后在不与任何已打包物品重叠的情况下，尽量向左移动。 注意，BL不是一个面向级别的打包算法。 时间复杂度。 O(n^2). 近似比。 BL(I) <=3·OPT(I)。

5. Baker'的Up-Down（UD）算法。 UD使用BL和NFDH的组合。 带状物和物品的宽度都被归一化，使带状物为单位宽度。 UD按非递增的宽度排序，然后将物品分成五组，每组的宽度范围为（1/2，1]，（1/3，1/2]，（1/4，1/3]，（1/5，1/4]，（0，1/5]。 带状物也分为五个区域R1，··· , R5. 基本上，在(1/i+1，1/i]的范围内，对于1 <= i <= 4，一些宽度的项目被BL打包到区域Ri。 由于BL在条带的右侧留下了一个从上到下宽度递增的空间，UD利用这个优势，首先将j=1，··&#183。 ，4（依次）从上到下。 如果没有这样的空间，则通过BL将物品打包到Ri。 最后，大小最多为1/5的物品被打包到R1，··&#183。 ，R4由（广义）NFDH算法。 同样如果这些区域没有空间，则使用NFDH将物品打包到R5。 近似比。 UD(I) <=(5/4) · OPT(I)+(53/8)H，其中H是物品的最大高度。 5/4的渐近边界很紧。

6. 反向拟合（RF）算法 RF还将带材和物品的宽度标准化，使带材具有单位宽度。 RF首先将所有宽度大于1/2的物品进行堆叠。 其余物品按非递增高度排序，并将高于大于1/2的物品所达到的高度H0进行打包。 然后RF重复下面的过程。 大致来说，RF将物品从左到右，底部沿着高度H0的线打包，直到没有空间为止。 然后从右到左，从上到下打包物品（称为反向水平），直到总宽度至少为1/2。 然后逆向水平面下降，直到（至少）其中一个接触到下面的某个物品。 以某种方式重复下拉。 近似比。 RF(I) <=2·OPT(I).

7. 斯坦伯格'的算法 Steinberg'的算法，在论文中表示为M，估计出一个包装所有物品所需高度H的上界，从而证明输入的物品可以被包装成一个宽度为W，高度为H的矩形。 然后他们定义了7个程序（有7个条件），每个程序将一个问题分成两个较小的问题，并递归解决。 已经证明，任何一个可解决的问题都满足这七个条件中的一个。 近似比。 M(I) <=2·OPT(I).

8. 分割-拟合算法(SF) SF将物品分为两组，宽度大于1/2的L1和最多1/2的L2。 L1的所有物品先由FFDH打包。 然后将它们排列成宽度大于2/3的物品都在宽度最多2/3的物品下面。 这样就形成了一个宽度为1/3的矩形R。 然后将L2中剩余的项目用FFDH打包到R和L1打包的项目上面的空间。 在R中创建的层次被认为是在L1的包装上方创建的层次之下。 近似比。 SF(I) <= (3/2) ·OPT(I) + 2; 3/2的渐近约束是紧密的。

9. Sleator'的算法 Sleater'的算法包括四个步骤。

10. 所有宽度大于1/2的物品都在条带底部互相打包。 假设h0是所得包装的高度 所有后续的包装将发生在h0之上。

11. 其余物品按高度不递增的顺序排列。 一级物品沿高度h0的线从左到右打包（按非递增高度顺序）。

12. 然后在中间画一条垂直线，将条带切成相等的两半（注意这条线可能会切掉右半部分包装的物品）。 画两条长度为二分之一的水平线段，一条横过左半边（称为左基线），一条横过右半边（称为右基线），尽量画得低一些，使两条线不与任何物品交叉。

13. 选择高度较低的左或右基线，将一级物品装入相应的半条，直到下一个物品太宽。 形成一条新的基线，在较低的基线上重复步骤(4)，直到所有物品都打包完毕。 时间复杂度。 O(n ·log n). Sleator'算法的近似比为2.5，很紧密。

速战速决的第一关方案总是一个很好的开始，如果没有其他原因，作为对比。

从大到小的贪婪放置。

把剩下的最大的长方形放到你的包装区域。 如果它在任何地方都放不下，就把它放在一个尽可能少地扩展包装区域的地方。 重复，直到你用最小的矩形完成。

它'一点也不完美，但它'很简单，是一个很好的基线。 它仍然会完美地包装你原来的例子，并为第二个例子也给你一个等价的答案。

请看一下包装问题。我认为你的问题属于'二维箱包装。'你应该能从这个问题和其他包装问题的解决方案中学到很多。

也请看。将矩形图像数据打包成方形纹理 。

关于这个问题有大量的文献。 一个好的贪婪的启发式方法是将矩形从最大的面积到最小的面积放在容器底部和左侧的第一个可用位置。 想象一下重力将所有的物品拉到左下角。 对于这个的描述，谷歌"查泽尔左下角包装"。

对于最佳解决方案，最先进的技术可以在几秒钟内打包20多个矩形。 Huang有一个算法 它将寻找最小包围边界框的问题与决定一组矩形是否能装入特定大小的边界框的问题分开。 你给他的程序一组矩形，它就会告诉你收拾这些矩形所需的最小包围边界盒。

对于你的情况，你的外循环应该从最小的可能的边界框向上迭代（宽度和高度依次以2的幂数增加）。 对于这些边界框中的每一个，测试是否可以为你的矩形找到一个包装。 你会得到一堆"no&quot。 答案，直到第一个"yes&quot。 答案，它将被保证是最优解。

对于你算法的内循环--回答"yes" 或"no" 到一个特定大小的边界框的那个循环，我会查找Huang的参考文献，然后直接实现他的算法。 他在基本算法的基础上加入了很多优化，但你真正需要的只是基本的肉和土豆。 既然你要处理旋转，在搜索过程中的每一个分支点，只需尝试两种旋转，当两种旋转都没有得到解时，就回溯。

我相当肯定这是一个NP-hard问题，因此，对于一个最佳解决方案，你必须实现一个回溯算法，尝试每一个可能的组合。

好消息是，由于需要在有限的二维空间中包装二维矩形，你可以在早期就修剪掉很多可能性，所以它可能不是那么糟糕。

你需要的是在 https://github.com/nothings/stb/blob/master/stb_rect_pack.h

样品。

stbrp_context context;

struct stbrp_rect rects[100];

for (int i=0; i< 100; i++)
{
    rects[i].id = i;
    rects[i].w = 100+i;
    rects[i].h = 100+i;
    rects[i].x = 0;
    rects[i].y = 0;
    rects[i].was_packed = 0;
}

int rectsLength = sizeof(rects)/sizeof(rects[0]);

int nodeCount = 4096*2;
struct stbrp_node nodes[nodeCount];

stbrp_init_target(&context, 4096, 4096, nodes, nodeCount);
stbrp_pack_rects(&context, rects, rectsLength);

for (int i=0; i< 100; i++)
{
    printf("rect %i (%hu,%hu) was_packed=%i\n", rects[i].id, rects[i].x, rects[i].y, rects[i].was_packed);
}

一般的解决方案是不难的（数学上的说法是完全**** 不可能）。 一般来说，人们使用遗传算法来尝试可能的组合，但你可以通过先把最大的形状放进去，然后为下一个最大的形状尝试不同的地方，这样就可以做得很好。

我'正在使用的是来自。

https://codereview.stackexchange.com/questions/179565/incremental-2d-rectangle-bin-packer?newreg=cce6c6101cf349c58423058762fa12b2

它实现了断头台算法，要求输入一个维度，并试图优化另一个维度（你也可以在代码中稍作修改设置一个最大值）。 也许如果你尝试两个值的不同功率，它将为你工作。

它在任何方面都不是最优的，但它体积小，可移植性强（只有.h），而且除了C++和STL之外没有其他依赖性。