Re: help with nesting

This smells very much like an NP-complete problem. I'd be very surprised if the problem isn't known in the literature. I am although a bit confused by the 'least amount of wasted space' requirement. If you have 4 4x6 and 6 2x9 rectangles, it's going to take 252 area. If your big rectangle has area N, and the smaller rectangles fit, you will be wasting N - 252 space. No matter how you fit them.

Abigail

Comment on Re: help with nesting

Replies are listed 'Best First'.
Re: Re: help with nesting by dragonchild (Archbishop) on Oct 01, 2003 at 15:24 UTC
The question is how close can (N - 252) -> 0? This problem isn't NP-complete. I'll post a solution after lunch. ------ We are the carpenters and bricklayers of the Information Age. The idea is a little like C++ templates, except not quite so brain-meltingly complicated. -- TheDamian, Exegesis 6 Please remember that I'm crufty and crochety. All opinions are purely mine and all code is untested, unless otherwise specified.	[reply]
Re: Re: Re: help with nesting by BrowserUk (Patriarch) on Oct 01, 2003 at 15:52 UTC
According to NIST, the Cutting Stock Problem is NP-Complete. The are several agressive optimisations that can be applied, but the basic status of the problem remains...unless you know different:) Examine what is said, not who speaks. "Efficiency is intelligent laziness." -David Dunham "When I'm working on a problem, I never think about beauty. I think only how to solve the problem. But when I have finished, if the solution is not beautiful, I know it is wrong." -Richard Buckminster Fuller If I understand your problem, I can solve it! Of course, the same can be said for you.	[reply]
Re4: help with nesting by dragonchild (Archbishop) on Oct 01, 2003 at 16:30 UTC
This is very similar to analyzing alpha-beta trees using Treemaps. That problem isn't NP-complete. It's just annoying. :-) ------ We are the carpenters and bricklayers of the Information Age. The idea is a little like C++ templates, except not quite so brain-meltingly complicated. -- TheDamian, Exegesis 6 Please remember that I'm crufty and crochety. All opinions are purely mine and all code is untested, unless otherwise specified.	[reply]