Programmers Contest: Fit pictures on a page

[tassach at gmail.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.
>
> -Don

For photos, it's a lot simpler, assuming you only want make standard
size prints (IE: 8x10, 5x7, 4x6, 2.5x3.5).  There are a very limited
number of combinations of the standard print sizes which will fit on an
8.5x11 sheet of paper.  This could probably be solved pretty easily
with just a lookup table.

Also, you have to remember that paper cost is only part of the equation
when printing photos -- you also have to consider ink costs.  In the
stock cutting problem, it's assumed that the cutting cost is
insignificant.  Given the insane cartidge costs for inkjet printers,
wasting a little paper -- even expensive paper -- is likely to be a
more economical than wasting ink.