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