Given a number of rectangles that can be rotated, find an enclosing rectangle of minimum area

So, I'm trying to implement an algorithm that takes in a number of rectangles as input and tries to pack them into a rectangle of minimum area. The rectangles can all be rotated by 90 degrees.

I realize that this is similar to the bin packing problem, but I am unable to find a good algorithm that accounts for the rotation. I found a paper that discusses this at length here and while I understand the article itself, I was hoping to find something simpler.

Any suggestions?

-Edit-

I think I misstated the problem earlier. We are given a开发者_JAVA百科 number of rectangles, such that each can be rotated by 90 degrees. We need to find a rectangle that fits all the given rectangles such that no two rectangles overlap, while minimizing the area of the enclosing rectangle.

The problem I face here is that we are asked to find the minimum, as opposed to being given an enclosing rectangle and checking if the given rectangles fit or something of that sort.

I've had good results using this algorithm:

http://www.intechopen.com/articles/show/title/a_greedy_algorithm_with_forward-looking_strategy

Edit:

The algorithm described in the link I supplied will give you a "Yes" or "No" answer as to whether a given set of rectangles can be packed into a specific enclosing rectangle. To find the minimum enclosing rectangle, you can run the algorithm repeatedly. Basically, calculate a lower bound and upper bound for the enclosing rectangle, then do a binary search to find the minimum solution that falls within those bounds. I'm assuming that the enclosing rectangle is a fixed size in one dimension (i.e., width is constant, looking for minimum length or vice versa). If both the width and length of the enclosing rectangle are allowed to vary, then it's more difficult and this may not work.

A simple (but naive) approach to calculating a lower bound and upper bound would be as follows:

Lower Bound - The best case is that all rectangles can be packed perfectly without any wasted space. So, sum the area of all input rectangles and calculate the enclosing rectangle length required for that area.

Upper Bounds - The worst case is that each rectangle must be packed on a separate "row", so for each input rectangle, calculate min(width, height) and sum those (i.e., pretend input rectangles are stacked upon one another using the minimum width or height of each input such that the other dimension of the input does not exceed the width of the enclosing rectangle).

If you work a little harder, you can improve the lower and upper bounds significantly to cut down on the search space, but this should give you starting point.