Maximizing the Number of Rectangles

Date: 10/26/2000 at 03:32:59
From: Bryan Santiago
Subject: Maximizing paper use

Hi! I have been trying to devise a method of cutting up a sheet of 
rectangular paper into smaller rectangular pieces of equal sizes. Say 
I have a sheet that is L x W big and I need pieces that are A x B 
small. How many pieces can I get?

The system I have now uses this method (L > W, A > B). It divides the 
paper into a grid of pieces of dimensions A x B. If any of the paper 
is left over, it divides the rest into a grid of B x A pieces. Then it 
adds up all the pieces.

     x1 = L/A
     y1 = W/B
     x2 = L-A*x1/W
     y2 = W/A
     outA = (x1*y1) + (x2*y2)

Sometimes this is not efficient, so I repeat the process with A and B 
switched.

     x3 = L/B
     y3 = W/A
     x4 = W-B*y3/L
     y4 = W/B
     outB = (x3*y3) + (x4*y4)

I use whichever is larger, outA or outB. Though this works most of the 
time, I have found exceptions.

For example, say I have a sheet of paper that is 13x8 and I need 
pieces that are 3x2.

     outA = (4*4) + (0*2) = 16
     outB = (6*2) + (0*4) = 12

It seems that 16 is the maximum, but I have discovered that you can 
rearrange the pieces in order to get 17. I have no idea how to compute 
for this. I need the information for a Java applet I am working on 
that gives you the maximum number of pieces you can get and at the 
same time draws the orientation of the pieces.

Date: 10/26/2000 at 17:10:26
From: Doctor Rob
Subject: Re: Maximizing paper use

Thanks for writing to Ask Dr. Math, Bryan.

The problem you are faced with is, in general, a very difficult one. 
It is a two-dimensional version of a famous one-dimensional problem 
called the Knapsack Problem. The Knapsack Problem has been proved to 
be in complexity class NP-complete. That means that the hardest 
Knapsack Problems are believed to take exponential time to solve. Of 
course, there are easy instances (fitting 1x1 rectangles in a 8x13 
rectangle is pretty easy).

There is an upper bound that you can easily compute. Divide the area 
of the large rectangle by the area of the small rectangle. The number 
of small ones cannot exceed this bound. 13*8/(3*2) = 104/6 = 17.333, 
so one cannot fit more than 17 3x2 rectangles into a 13x8 rectangle. 
This tells you nothing about the actual layout, of course.

An additional complicating factor is that occasionally it is 
advantageous to put the small rectangles with their sides NOT parallel 
to the sides of the large rectangle. For a 13x8 rectangle, a 14x1 
rectangle won't fit with sides parallel, but it will fit diagonally 
(actually, two will fit).

Probably there is a theorem that says that if the large rectangle's 
dimensions are large enough with respect to the small rectangle's 
dimensions, then the maximum number allowable by the area bound will 
be possible to find with all sides parallel. The way to show that such 
a theorem is true is to cut the large rectangle up into smaller 
rectangular pieces that can be cut up into small rectangles with no 
waste, except for one remaining piece whose area is smaller than that 
of the small rectangles.

In the case you cite, you can cut off a 9x8 rectangle from your 13x8 
rectangle. That can be cut into small rectangles with no waste 
(3*3 = 9, 4*2 = 8, so 3*4 = 12 small rectangles aligned horizontally 
will do it). That leaves a 4x8 rectangle. From this you can cut off a 
4x6 piece that can be formed from four small rectangles vertically 
aligned, leaving a 4x2 piece. From this piece you can cut off a 3x2 
piece which is one small rectangle horizontally aligned, leaving a 1x2 
piece that is wasted. That gives you the 17 small rectangles.

The trick is to find the way to cut the large rectangle into these 
efficient pieces.

Sorry, but this seems very hard to do algorithmically.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/