Seems to me that there will be a limited solution space to explore. You can define a set of "optimal" classes of solutions based on the presence of space hogs.

So, given 8x10 paper (first restriction) and the potential sizes 3.5x5, 4x6, 5x7, 8x10 (second restriction):

8x10 is straightforward, a derivative case with only 1 solution.

Given the presence of a 5x7, the set of solution classes will involve either 1 more 5x7 or two 3.5x5 photos.

Given the presence of a 4x6, the set of solution classes will involve either one more 4x6 and a 3.5x5 or 2 3.5x5 photos.

There will be only one maximal solution for sets composed of only 3.5x5 (there will actually be multiple maximal solution classes which vary in the details of the layout, but as for the actual count of photos they will be equivalent. Just pick the one that ends up being less effort to cut after printing).

So given your whole pile of images, the source set, start with the largest ones. For each "largest" photo, pull smaller photos from the pool in order to construct your solution class, given the size of your initial photo.

In the case of 4x6, I'm not sure whether it's optimal to cluster the 4x6's with each other or always fill the space with 3.5x5 photos. That's one vaguary that arises in this limited version of the general problem that you can crank on yourself. Plus I've sort of assumed here that the supply of 3.5x5 photos are plentiful compared to the larger ones. That might be a large assumption.

As for the general problem -- lots of reading suggestions for the generic algorithms have been suggested here. If you want to tackle truly variable-sized photos on variable-sized paper, you're on your own!

Cool question, btw, ++. And when you come up with a perl solution, post it because I'll be wanting to use it. ;-)

Matt

In reply to Re: Rectangle packing... by mojotoad
in thread Rectangle packing... by suaveant

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.