|
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
Navigation:
[Reply to this message]
|