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

  • $\begingroup$ Have you even tried to pack them? Note that dimensions can be divided by two to make things easier. $\endgroup$ – Parcly Taxel Aug 15 '16 at 16:13
  • $\begingroup$ Is it a 72X72 big rectangle? Do you need to fit all the rectangles in it? Does this means that the area of the rectangle equals the sum of the smaller ones? $\endgroup$ – Moti Aug 15 '16 at 16:54
  • $\begingroup$ i am flexible with width of rectangle. Height needs to be 72" . area of bigger rectangle can be more, giving space for a couple or two more small rectangles $\endgroup$ – N Jain Aug 15 '16 at 17:55

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$ Optimal packing of rectangles

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.