找到包含所有矩形的最小区域

Question

这是一个面试问题.
我们给出了各种矩形的尺寸,我们必须找出可以包围所有矩形的矩形区域(最小值)？矩形也可以旋转.

test case:-
input:
3   //number of rectangles
8 8
4 3
3 4

output:
88

11x8:
+ - - - - - - + + - +
|             | |   |
|             | |   |
|             | + - +
|             | + - +
|             | |   |
|             | |   |
+ - - - - - - + + - +

我在最小可能区域中拟合矩形 之前查看了一个类似的问题
,上述方法着眼于所有可能性,旋转,并确定所有布局情况下所有这些可能性的最小值.
我们不能建立一个算法,我们首先找到矩形区域的总和,然后寻找最大长度,宽度？

Answer 1

这个问题没有绝对的解决方案,但有几种近似的解决方案,你可以在这里阅读其中的一些解决方案.

Answer 2

非方形基准上的最佳矩形包装:

给定一组矩形,我们的问题是找到包含它们的最小区域的所有包围矩形而没有重叠.我们将封闭的矩形称为边界框.优化问题是NP难的,而决定一组矩形是否可以在给定的边界框中打包的问题是NP完全的,通过从bin-packing减少(Korf 2003).

最佳矩形填料的新改进:

Korf [2003]将矩形包装问题分为两个子问题:最小边界框问题和包含问题.前者找到一个最小区域的边界框,可以包含一组给定的矩形,而后者则尝试将给定的矩形打包在给定的边界框中.解决最小边界框问题的算法将解决包含问题的算法称为子例程.

最小边界框问题

解决最小边界框问题的一种简单方法是找到描述可行和可能最佳边界框集的最小和最大区域.可以使用该范围内的区域生成所有维度的边界框,然后以非递减的面积顺序进行测试,直到找到所有可行的最小区域的解.最小面积是给定矩形的面积之和.最大面积由贪婪解决方案的边界框确定,该边界框通过将边界框高度设置为最高矩形的高度,然后在从左到右扫描时将矩形放在第一个可用位置,并从从下到上.

另请参见最佳矩形填充:新结果.