Fitting smaller rectangles into bigger

Question

I need to fit following rectangles into one big rectangle of N" * 72".

Length * width - No of rectangles of this dimension

20" * 18" - 4 count.

12" * 12" - 6 count.

24" * 6" - 2 count.

20" * 8" - 2 count.

16" * 12" - 6 count.

8" * 10 " - 4 count.

12" * 6" - 4 count.

12" * 8" - 4 count.

12" * 10" - 4 count.

10" * 6" - 10 count.

we can have a few rectangles little bigger to make it fit in a complete rectangle. If given a choice, I would prefer a haphazard configuration. Can anyone please help us ? Thanks

Answer 1

There are three observations one can make about your set of rectangles.

1. Their total area is $6136$.
2. The width of them are all even integers.
3. Except the ten rectangles with dimension $10 \times 6$, the width of the rest are multiples of $4$.

If you are going to pack the rectangle so that they are axis-aligned and don't allow them to rotate, then using $(1)$ and $(2)$, one can show that $$N \ge 2 \left\lceil \frac12 \times \frac{6136}{72}\right\rceil = 86$$

If more than two of the ten rectangles with dimension $10 \times 6$ lies on a horizontal line, then using $(3)$, one can show that it is impossible to fit all the rectangles into a $86 \times 72$ rectangle.

In order to obtain an optimal packing (i.e one with $N = 86$), this suggest one should try to align the ten rectangles as vertically as possible. With this as a hint, I am able to construct following optimal packing by hand.

$\hspace1in$

We are lucky this time. In general, the problem of packing rectangles optimally is known to be NP-hard.

If you want to obtain other packing of these rectangles or packing other rectangles but only need an near optimal solution, there are commercial software which does the job. If you want to learn how to do that yourself, look at answers of this related question on stackoverflow as a start.