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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.