Programmers Contest: Fit pictures on a page

[Roy Smith]

In article <42c32af7 at usenet01.boi.hp.com>,
 Don <donald.welch at NOSPAM.hp.com> wrote:

> 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

Not just plywood panels, but sheets of paper, bolts of cloth, sheet metal, 
plate glass, etc.  A slight complication is that some materials have a 
preferred orientation (i.e. plywood has a grain, textiles have warp vs. 
weft, etc) and some don't (or it doesn't matter for the application).

It gets even more interesting when you're restricted to making cuts that 
start at an edge, or go all the way through the sheet to the other side.

My first introduction to the problem was helping my grandmother cut cookies 
out of a sheet of dough.  I can't think of a better way to get introduced 
to higher math :-)