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

Question

这是一道面试题。
给定各种矩形的尺寸，我们必须找出可以包围所有这些矩形的面积(最小)？矩形也可以旋转。

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

output:
88

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

我看了之前问过的类似问题 fitting rectangles in the smallest possible area
上述方法着眼于所有可能性、旋转，并确定所有布局情况下所有此类可能性的最小值。
我们不能建立一个算法，首先找到矩形的面积总和，然后寻找最大长度和宽度吗？

Answer 1

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