关于这个问题有大量的文献。一种好的贪婪启发式方法是将矩形从大到小放置在容器底部和左侧的第一个可用位置上。想象重力把所有的东西都拉到左下角。对于这个谷歌“沙雷左下角包装”的描述。

为了获得最佳解决方案，最先进的技术可以在几秒钟内完成20多个矩形。Huang有一种算法，可以将寻找最小的外围包围框的问题与确定一组矩形是否适合特定大小的包围框的问题分开。你给他的程序一组矩形，它会告诉你打包这些矩形所需要的最小的包围框。

对于您的情况，外部循环应该从最小的边界框向上迭代(宽度和高度依次以2的幂增加)。对于每个包围框，测试一下是否可以为矩形找到一个填充。你会得到一堆“不”的答案，直到第一个“是”的答案，这将保证是最优解。

对于算法的内部循环——对特定大小的边界框回答“是”或“否”的循环，我将查找Huang参考并实现他的算法。他在基本算法的基础上进行了大量优化，但你只需要最基本的部分。由于您希望处理旋转，因此在搜索过程中的每个分支点上，只要同时尝试两个旋转并在两个旋转都没有得到解决方案时回溯即可。

我相当确定这是一个np困难的问题，因此，为了获得最优解决方案，您必须实现一个回溯算法，尝试所有可能的组合。

好消息是，由于需要在有限的2D空间中填充2D矩形，你可以在早期删除许多可能性，所以这可能并不是那么糟糕。

关于这个问题有大量的文献。一种好的贪婪启发式方法是将矩形从大到小放置在容器底部和左侧的第一个可用位置上。想象重力把所有的东西都拉到左下角。对于这个谷歌“沙雷左下角包装”的描述。

为了获得最佳解决方案，最先进的技术可以在几秒钟内完成20多个矩形。Huang有一种算法，可以将寻找最小的外围包围框的问题与确定一组矩形是否适合特定大小的包围框的问题分开。你给他的程序一组矩形，它会告诉你打包这些矩形所需要的最小的包围框。

对于您的情况，外部循环应该从最小的边界框向上迭代(宽度和高度依次以2的幂增加)。对于每个包围框，测试一下是否可以为矩形找到一个填充。你会得到一堆“不”的答案，直到第一个“是”的答案，这将保证是最优解。

对于算法的内部循环——对特定大小的边界框回答“是”或“否”的循环，我将查找Huang参考并实现他的算法。他在基本算法的基础上进行了大量优化，但你只需要最基本的部分。由于您希望处理旋转，因此在搜索过程中的每个分支点上，只要同时尝试两个旋转并在两个旋转都没有得到解决方案时回溯即可。

关于解决方案的调查，请参阅ARC项目的本页，在实现复杂性/时间和最优性之间存在权衡，但有广泛的算法可供选择。

以下是算法的摘录:

First-Fit Decreasing Height (FFDH) algorithm FFDH packs the next item R (in non-increasing height) on the first level where R fits. If no level can accommodate R, a new level is created. Time complexity of FFDH: O(n·log n). Approximation ratio: FFDH(I)<=(17/10)·OPT(I)+1; the asymptotic bound of 17/10 is tight. Next-Fit Decreasing Height (NFDH) algorithm NFDH packs the next item R (in non-increasing height) on the current level if R fits. Otherwise, the current level is "closed" and a new level is created. Time complexity: O(n·log n). Approximation ratio: NFDH(I) <= 2·OPT(I)+1; the asymptotic bound of 2 is tight. Best-Fit Decreasing Height (BFDH) algorithm BFDH packs the next item R (in non-increasing height) on the level, among those that can accommodate R, for which the residual horizontal space is the minimum. If no level can accommodate R, a new level is created. Bottom-Left (BL) Algorithm BL first order items by non-increasing width. BL packs the next item as near to the bottom as it will fit and then as close to the left as it can go without overlapping with any packed item. Note that BL is not a level-oriented packing algorithm. Time complexity: O(n^2). Approximation ratio: BL(I) <= 3·OPT(I). Baker's Up-Down (UD) algorithm UD uses a combination of BL and a generalization of NFDH. The width of the strip and the items are normalized so that the strip is of unit width. UD orders the items in non-increasing width and then divides the items into five groups, each with width in the range (1/2, 1], (1/3,1/2], (1/4,1/3], (1/5,1/4], (0,1/5]. The strip is also divided into five regions R1, ··· , R5. Basically, some items of width in the range (1/i+1, 1/i], for 1 <= i <= 4, are packed to region Ri by BL. Since BL leaves a space of increasing width from top to bottom at the right side of the strip, UD takes this advantage by first packing the item to Rj for j = 1, ··· , 4 (in order) from top to bottom. If there is no such space, the item is packed to Ri by BL. Finally, items of size at most 1/5 are packed to the spaces in R1, ··· , R4 by the (generalized) NFDH algorithm. Again if there is no space in these regions, the item is packed to R5 using NFDH. Approximation ratio: UD(I) <= (5/4) · OPT(I)+(53/8)H, where H is the maximum height of the items; the asymptotic bound of 5/4 is tight. Reverse-fit (RF) algorithm RF also normalizes the width of the strip and the items so that the strip is of unit width. RF first stacks all items of width greater than 1/2. Remaining items are sorted in non-increasing height and will be packed above the height H0 reached by those greater than 1/2. Then RF repeats the following process. Roughly speaking, RF packs items from left to right with their bottom along the line of height H0 until there is no more room. Then packs items from right to left and from top to bottom (called reverse-level) until the total width is at least 1/2. Then the reverse-level is dropped down until (at least) one of them touches some item below. The drop down is somehow repeated. Approximation ratio: RF(I) <= 2·OPT(I). Steinberg's algorithm Steinberg's algorithm, denoted as M in the paper, estimates an upper bound of the height H required to pack all the items such that it is proved that the input items can be packed into a rectangle of width W and height H. They then define seven procedures (with seven conditions), each to divide a problem into two smaller ones and solve them recursively. It has been showed that any tractable problem satisfies one of the seven conditions. Approximation ratio: M(I) <= 2·OPT(I). Split-Fit algorithm (SF) SF divides items into two groups, L1 with width greater than 1/2 and L2 at most 1/2. All items of L1 are first packed by FFDH. Then they are arranged so that all items with width more than 2/3 are below those with width at most 2/3. This creates a rectangle R of space with width 1/3. Remaining items in L2 are then packed to R and the space above those packed with L1 using FFDH. The levels created in R are considered to be below those created above the packing of L1. Approximation ratio: SF(I) <= (3/2) ·OPT(I) + 2; the asymptotic bound of 3/2 is tight. Sleator's algorithm Sleater's algorithm consists of four steps: All items of width greater than 1/2 are packed on top of one another in the bottom of the strip. Suppose h0 is the height of the resulting packing All subsequent packing will occur above h0. Remaining items are ordered by non-increasing height. A level of items are packed (in non-increasing height order) from left to right along the line of height h0. A vertical line is then drawn in the middle to cut the strip into two equal halves (note this line may cut an item that is packed partially in the right half). Draw two horizontal line segments of length one half, one across the left half (called the left baseline) and one across the right half (called the right baseline) as low as possible such that the two lines do not cross any item. Choose the left or right baseline which is of a lower height and pack a level of items into the corresponding half of the strip until the next item is too wide. A new baseline is formed and Step (4) is repeated on the lower baseline until all items are packed. Time complexity: O(n ·log n). The approximation ratio of Sleator's algorithm is 2.5 which is tight.

快速和肮脏的第一遍解决方案总是一个很好的开始，如果没有其他的比较。

贪心安置由大到小。

把剩下的最大的矩形放入打包区域。如果它放不下任何地方，就把它放在一个尽可能不扩大背包区域的地方。重复这一步骤，直到你完成最小的矩形。

它一点也不完美，但它很简单，是一个很好的底线。它仍然会完美地包装你原来的例子，并为第二个例子提供相同的答案。

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