Posted by Don on 06/30/05 02:07

Chung Leong wrote:

> Isn't that an NP-complete problem or am I crazy?

It is NP complete. Its known as the "cutting stock problem" (aka "Knapsack
problem"). Here's a Wikipedia page that describes it:

http://en.wikipedia.org/wiki/Cutting_stock_problem

There are commerical applications available that "solve" the problem in 2D
for use in the woodworking industry (among others). This is generally done
to minimize waste when cutting down panels (plywood, etc) into smaller
pieces for cabinets, etc.

-Don

[Back to original message]