Re: Nesting 2

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

Comment on Re: Nesting 2

Replies are listed 'Best First'.
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]

Replies are listed 'Best First'.

Re: Re: Nesting 2
by jdtoronto (Prior) on Dec 02, 2003 at 20:06 UTC

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]