Nesting 2

stu96art has asked for the wisdom of the Perl Monks concerning the following question:

I will start by giving the data that I have available. I have a list of rectangles of all different sizes, some small, medium, and large. I also have different sizes of glass that these rectangles must be cut out of. I am trying to use as much of the glass as possible, for the highest yield. First, there is one factor that must be taken care of. There must be a single line that runs either horizontal or vertical, all across the glass. after this factor is met, the remaining area is filled with the remaining rectangles. Then once there are no more rectangles that will fit, we see what the yield is and try another combination of rectangles, and then compare the yields, going with the highest yield. I am looking to have several different combinations, but I do not know how to go about creating them, or how I could re-create them once the one with the largest yield is found. Could anyone please help me?? Thanks. For example, let's say I have 80 rectangles 40 small, 27 medium, and 13 large. All of the small are not the same size, but are "small" in comparison. I would like to avoid having all of the small rectangles on one sheet and we will say that one sheet can hold about 20 medium, 30 small, or 10 large. I am looking to use either the x, or y dimension to first create this straight line, either horizontal or vertical. Then fill in the remaining area. I hope that this makes sense, and that I can get some help. Any help would be greatly appreciated.

Comment on Nesting 2

Replies are listed 'Best First'.
Re: Nesting 2 by jdtoronto (Prior) on Dec 02, 2003 at 16:33 UTC
Try this website: KnapSack problem I think it will give you some of the mathematical foundation of the problem. jdtoronto	[reply]
Re: Nesting 2 by duff (Parson) on Dec 02, 2003 at 16:21 UTC
Sounds like a variation of the knapsack problem to me. Ask google about it and search CPAN for modules P.S., where's the Perl in this problem? PerlJam	[reply]
Re: Nesting 2 by Abigail-II (Bishop) on Dec 02, 2003 at 17:18 UTC
As pointed out, this looks like a variation of the knapsack problem (although I've no idea what the purpose of the single line is). The knapsack problem is a well studied problem, and it is a really hard problem. What is the background of your particular instance of this problem? Abigail	[reply]
Re: Re: Nesting 2 by jdtoronto (Prior) on Dec 02, 2003 at 20:06 UTC
As the seeker says, he wants to cut sheets of glass. I think he is looking to cut his own reference edge then go from there. It is solvable but it is NP-hard! I do recall seeing something in the Perl world related to a similar problem. The seeker might look up WARDLEY on CPAN, I think Andy may have done something for optimizing fabric cut-out for kite building. A good reference on the problem can be found at: "Algorithms and Theory of Computation Handbook", page 19-27, Copyright © 1999 by CRC Press LLC. Which also appears in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC. jdtoronto	[reply]