Programmers Contest: Fit pictures on a page
Don
donald.welch at NOSPAM.hp.com
Wed Jun 29 19:07:30 EDT 2005
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
More information about the Python-list
mailing list