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. -- http://mail.python.org/mailman/listinfo/python-list
