什么算法可用于在一个相当最佳的方式包装不同大小的矩形到最小矩形可能吗？(What algorithm

Ive得到了一堆，我需要打包成尽可能小的空间（这个空间的尺寸应该是两个大国）的矩形对象。

我所知道的各种包装的算法，将包中的项目，以及可能在给定的空间，但是在这种情况下，我需要的算法，制定出空间应该多大为好。

例如说，香港专业教育学院得到了以下的矩形

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:

快速和肮脏的第一通解决方案始终是一个伟大的下手，因为如果没有别的比较。

贪婪的放置由大变小。

把剩下的到您的打包面积最大的矩形。如果它不适合在任何地方，将其放置在扩展尽可能少的包区域的地方。重复，直到你用最小的矩形完成。

它并不完美可言，但它很容易和一个不错的基线。它仍然会收拾你的原来的例子完美，给你第二等效答案为好。

Answer 2:

见在ARC项目这个页面的解决方案的调查，目前实现的复杂度/时间和最优之间的权衡，但有一个广泛的算法选择。

下面是该算法的摘录：

首次适应降低的高度（FFDH）算法
FFDH包上，其中R适合的第一电平的下一个项目R（非高度增加）。如果没有电平可容纳R，创建了新的水平。
时间FFDH的复杂度：O（N·log n）的。
逼近比：FFDH（I）<=（17/10）·OPT（I）1; 约束的17/10渐近紧。
接着合式降低的高度（NFDH）算法
NFDH包上的电流电平的下一个项目R（非高度增加）如果R嵌合。否则，目前的水平是“关闭”和一个新的水平被创建。
时间复杂度：O（N·log n）的。
逼近比：NFDH（I）<= 2·OPT（I）1; 结合的2的渐近是紧的。
最合适的高度减小（BFDH）算法
BFDH包上水平，那些能够容纳R，的量，残留的水平空间为最小之间的下一个项目R（非高度增加）。如果没有电平可容纳R，创建了新的水平。
左下（BL）算法
非增加的宽度BL第一阶项。 BL包的下一个项目尽可能接近，因为它会适合，然后尽量靠近左边，因为它可以去没有任何包装的项目重叠的底部。需要注意的是BL不是面向级包装算法。
时间复杂度：O（N ^ 2）。
近似比：BL（I）<= 3·OPT（I）。
贝克的上下（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区域R1。由于BL离开在带材的右侧从顶部宽度增加至底部的空间，UD由第一取这个优点包装的项目为RJ从上到下J = 1，...，4（按顺序），如果不存在这样的空间，则该项目被BL填充至Ri。最后，大小的项至多1/5被打包到的空间中，R1，...，R4由（广义）NFDH算法。同样地，如果有在这些区域中没有空间时，该项目使用NFDH填充至R5。
逼近比：UD（I）<=（5/4）·OPT（I）+（53/8）H，其中H是项目的最大高度; 约束的5/4渐近紧。
反向配合（RF）算法
使得带材是单元宽度的RF也归一化条带的宽度和物品。 RF第一堆叠宽度大于1/2的所有项目。其余项目都在非增高度来分类，并且将那些大于1/2达到的高度H0上述包装。然后RF重复以下的处理。粗略地说，RF包从左至右他们沿着底部高度H0的行项目，直到有没有更多的空间。然后由右至左包项目和从顶部到底部（称为反向电平），直到总宽度至少为1/2。此后一直到（至少）其中一人之下倒是一些项目的反向电平降低下来。下拉以某种方式重复。
近似比：RF（I）<= 2·OPT（I）。
Steinberg的算法
Steinberg的算法，在纸表示为M，估计的上部结合到包装中的所有项目，使得它证明了输入项目可装入宽度W和高度H的矩形然后它们定义7所需要的高度H的程序（具有七个条件）中，每个划分的问题分成两个较小的并递归解决这些问题。它已经表明，任何听话的问题满足七个条件之一。
近似比：M（I）<= 2·OPT（I）。
分裂拟合算法（SF）SF至多1/2分项成两组，L1比1/2宽度和L2。 L1的所有项目都首先由FFDH包装。然后，他们被布置成与宽度的2/3以上所有项目都低于那些宽度至多2/3。这产生的空间宽度1/3的矩形R。然后在L2剩余项目被打包到R和上述那些装有使用FFDH L1的空间。作为R创建的水平被认为是低于L1的填料上方创建。
近似比：SF（I）<=（3/2）·OPT（I）+ 2; 结合的3/2的渐近是紧的。
Sleator算法
Sleater的算法包括四个步骤：
1. 宽度大于1/2的所有项目都在带的底部填充在彼此的顶部上。假设H0是所得包装的所有后续的包装会发生上述H0的高度。
2. 其余的项目是由非高度的增加而有序。项目的水平都挤满（非高度的增加顺序）由左到右沿高度H0的线。
3. 一条垂直线，然后在中间的条带切割成两个相等的两半（注意这线可以削减了在右半部分填充的项目）绘制。绘制长度的两个水平线段二分之一，跨过左半边（称为左基线）和一个穿过右半（称为右基线）尽可能低，使得两行不交叉的任何项目。
4. 选择左或右基线这是一个较低的高度的和包装物品的水平到所述条带的对应的半直到下一个项目是太宽。
一个新的基线，形成和步骤（4）重复上下基线，直到所有的数据项都包装。
时间复杂度：O（N·log n）的。
Sleator的算法的近似比为2.5，其是紧的。

Answer 3:

看看包装问题。我想你落在下“2D装箱。” 您应该能够从该解决方案以及其他的包装问题，学到很多东西。

也参见：包装矩形图像数据转换成一个正方形的纹理。

Answer 4:

目前在这个问题上广泛的文献。一个好的启发式贪婪是把从大面积最小的矩形朝容器的底部和左侧第一个可用的位置。想想重力牵引的所有项目到左下角的。对于这个谷歌的说明“Chazelle左下角包装”。

为了获得最佳的解决方案，国家的最先进的技术可以包在几秒钟内超过20的矩形。黄有一个算法，用于分隔决定一组矩形是否能够适应特定大小的边框的问题，找到的最小包围边框的问题。你给他的节目一组矩形，它告诉你收拾它们所需的最小包围边框。

对于你的情况，你的外循环迭代应该从最小的边框上方（与宽度和高度先后由二的幂增加）。对于这些边界框，看看测试，如果你能找到适合您的矩形包装。你会得到一堆“否”的回答，直到第一个“是”回答，这将保证是最佳的解决方案。

对于你的算法的内循环 - 即回答“是”或“否”，以特定大小的边界框的一个，我会抬头看黄参考，只是实施他的算法。他包括了很多基本的算法之上优化的，但你只有真正需要的基本的香饽饽。由于要处理的旋转，在搜索过程中的每个分支点，只是一味两个旋转和原路返回时，都转不解决造成的。

Answer 5:

我敢肯定，这是一个NP难问题，所以，对于一个最佳的解决方案，你必须执行，尝试一切可能的组合回溯算法。

好消息是，因为需要收拾2D矩形在有限的二维空间，你可以在早期修剪了很多的可能性，所以它可能不是那么糟糕。

Answer 6:

你需要的是在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);
}