Programmers Contest: Fit pictures on a page

[mensanator at aol.com]

Don 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.

Not the same. Read the contest rules. You are allowed to change the
size
and shape (do a certain degree). You certainly can't arbitrarily change
the sizes in a woodworking environment.

> 
> -Don