找到包含所有矩形的最小区域 [英] find smallest area that contains all the rectangles

问题描述

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

This is an interview question.
We are given dimensions of various rectangles, we have to find out the area(minimum) of rectangle that can enclose all of them? rectangles can be rotated also .

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

output:
88

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

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

i looked at a similar question asked before fitting rectangles in the smallest possible area
the above approach looks at all possibilities ,rotations, and determine the minimum over all such possibilities in all layout cases.
can't we base an algorithm in which we find the sum of area of rectangles first and then look for max length ,width?

推荐答案

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

There is no absolute solution to this problem, but there are several approximate solutions, you can read about some of them here.

这篇关于找到包含所有矩形的最小区域的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！