I did a bit of searching and found:

• This presentation (PowerPoint I'm afraid) which looks like a nice explanation of the tabu search method applied to the knapsack problem.
• Yehoshua Perl is a researcher who seems to come up often in reference to this type of problem

--
I'd like to be able to assign to an luser

Try googling for `two dimensional knapsack'. That gives some promising looking hits.

For the non-CS types in the audience, this type of problem is known as `the knapsack problem' because it's analagous to finding the largest amount of fixed sized objects weighing w_i units each that can fit in a bag that can hold x units.

Update: Glancing over some of the google results seems to indicate you've picked a doozy. Having a few fixed layouts for the groupings you're most likely to use probably would be the quicker solution.

Oh, and: Post #300. Wh00t.

it's an interesting problem to solve computationally, but it seems best left as an excersize.

3.5x5	4x6	5x7	8x10
			P
		LL
PP		L
P	LP
PPPP
...

~Particle ;Ş

Yeah... I've already started down that path... in that case I just have to work out something that finds the best combo for all the images I have to get them to fit in the least pages, which I know I can do... won't be fun, but will be a lot easier :)

                - Ant
                - Some of my best work - (1 2 3)

if($picture->size() eq "8x10") {
    # it's the only one that'll fit on 8.5x11
    $picture->print();
    return;
}
...
[download]

Seriously, that's an interesting problem; I'm looking forward to seeing the answers.

Edit:Did a bit of searching on google, with no luck until I followed the advice below and tried "two dimensional knapsack". But I did come across a commercial library, altough that looks targeted at much more generalized versions of the problem than yours...
--
Mike

One interesting note, which makes a lot of sense.

Dr. Math points out that the most items you can fit in is the area of the page divided by the area of the smallest item.

That means that you could never get more than 5 photos on a page no matter what you try (8.5x11/3.5x5 = 93.5/17.5 = 5), so that simplifies your search quite a bit...

Even with that case, it looks like you have to "waste" one photo worth of blank space, and you can only fit 4...
--
Mike

I read this:

     The problem of packing a set of items into a number of bins such that the total weight, volume, etc. does not exceed some maximum value. A simple algorithm (the first-fit algorithm) takes items in the order they come an places them in the first bin in which they fit. In 1973, J. Ullman proved that this algorithm can differ from an optimal packing by as much at 70% (Hoffman 1998, p. 171). An alternative strategy first orders the items from largest to smallest, then places them sequentially in the first bin in which they fit. In 1973, D. Johnson showed that this strategy is never suboptimal by more than 22%, and furthermore that no efficient bin-packing algorithm can be guaranteed to do better than 22% (Hoffman 1998, p. 172).

on this website: http://mathworld.wolfram.com/Bin-PackingProblem.html

Which seems to suggest that the absolute best answer will not always be sufficiently better than a fairly-good answer to justify the trouble of finding it.

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

Nice. I looked around for a little while but didn't find this. Certainly if it works it is worth 35 bucks... thanks! I may still play with mine... but I will certainly try the demo version of this...

                - Ant
                - Some of my best work - (1 2 3)

Heieiei, immer chunnt üsi Armee unger d'Reder... hrm
Sorry, some Swiss German there... :-) They have pocket knives, really, but even these things are pretty good at cutting stuff to pieces... :-P

--cs

There are nights when the wolves are silent and only the moon howls. - George Carlin

$canvas{width} = 8.5;
$canvas{height} = 11;
foreach(@pictures_to_canvas){
    if ( ($canvas{width} > $$_{width}) && ($canvas{height} > $$_{width
+}) {
        $canvas{width} -= $$_{width};
        $canvas{height} -= $$_{height};
    }
#Throw exception here if height or width goes below a min value.
}
...
[download]

The Page object maintains a list of openings. When a Rect is put in an opening, (up to) two new openings are made. Putting in Rect 'a' generates openings 'b' and 'c':

aaaabbbb
aaaabbbb
cccccccc
cccccccc

aaaabbbb
aaaabbbb
ccccdddd
ccccdddd

YuckFoo

#!/usr/bin/perl

   use strict;

   my ($WIDE, $HIGH) = qw(48 24);

   my ($rects, $rect, $page);

   # Make list of random rectangles
   for my $char ('a'..'z', 'A'..'Z') {

      my $wide = int(rand($WIDE/2)+1);
      my $high = int(rand($HIGH/2)+1);

      push (@{$rects}, Rect->new($wide, $high, $char));
   }

   # Sort list of rectangles
   $rects = Rect::sortrecs($rects);
   for $rect (@{$rects}) { $rect->show(); }

   # While there are rectangles, create a page and pack it
   while (@{$rects}) {
      $page = Page->new($WIDE, $HIGH);
      $rects = $page->packit($rects);
      $page->show();
   }

#-----------------------------------------------------------
package Page;
#-----------------------------------------------------------
sub new {

   my ($pkg, $wide, $high) = @_;

   my $r = {}; bless $r, $pkg;

   $r->{wide} = $wide;
   $r->{high} = $high;
   $r->{page} = [];
   $r->{open} = [];

   push (@{$r->{open}}, [0, 0, $wide-1, $high-1, $wide, $high]);

   $r->fill(0, 0, $wide, $high, '.');

   return $r;
}

#-----------------------------------------------------------
sub fill {

   my ($p, $begx, $begy, $endx, $endy, $char) = @_;

   for (my $y = $begy; $y < $begy+$endy; $y++) {
      for (my $x = $begx; $x < $begx+$endx; $x++) {
         $p->{page}[$x][$y] = $char;
      }
   }
}

#-----------------------------------------------------------
sub packit {
   
   my ($p, $rs) = @_;
   my (@notdone);
   
   for my $r (@{$rs}) {
      
      # Try packing rectangle into page
      my $done = packtry($p, $r);
      
      if ($done == -1) {
         
         # Flip rectangle and try again
         ($r->{wide}, $r->{high}) = ($r->{high}, $r->{wide});
         $done = packtry($p, $r);
      }
      if ($done >= 0) {

         my (@add, $nwx, $nwy, $sex, $sey, $wide, $high);

         # The opening that was used
         my $o = $p->{open}[$done];

         # Make new opening
         $nwx = $o->[0] + $r->{wide};
         $nwy = $o->[1];
         $sex = $o->[2];
         $sey = $o->[1] + $r->{high} - 1;
         $wide = $sex - $nwx + 1;
         $high = $sey - $nwy + 1;
         
         @add = ();
         if ($wide * $high > 0) {
            push (@add, [$nwx, $nwy, $sex, $sey, $wide, $high]);
         }
         
         # Make new opening
         $nwx = $o->[0];
         $nwy = $o->[1] + $r->{high};
         $sex = $o->[2];
         $sey = $o->[3];
         $wide = $sex - $nwx + 1;
         $high = $sey - $nwy + 1;
         
         if ($wide * $high > 0) {
            push (@add, [$nwx, $nwy, $sex, $sey, $wide, $high]);
         }
         
         # Replace old opening with new openings
         splice(@{$p->{open}}, $done, 1, @add);
         
         # to show each step
         # $p->show();
      }
      else {
         push(@notdone, $r);
      }
   }
   
   return \@notdone;
}

#-----------------------------------------------------------
sub packtry {

   my ($p, $r) = @_;

   for (my $i = 0; $i < @{$p->{open}}; $i++) {

      my $o = $p->{open}[$i];

      if ($r->{wide} <= $o->[4] && $r->{high} <= $o->[5]) { 
         $p->fill($o->[0], $o->[1], $r->{wide}, $r->{high}, $r->{char}
+);
         return($i);
      }
   }
   
   return (-1);
}

#-----------------------------------------------------------
sub show {
   
   my ($p) = @_;
   
   for (my $y = 0; $y < $p->{high}; $y++) {
      for (my $x = 0; $x < $p->{wide}; $x++) {
         print "$p->{page}[$x][$y]";
      }
      print "\n";
   }
   print "\n";
   
   for my $o (@{$p->{open}}) {
      print "open: $o->[0],$o->[1] ".
                  "$o->[2],$o->[3] ".
                  "$o->[4],$o->[5]\n";
   }
   print "\n";
}

#-----------------------------------------------------------
package Rect;
#-----------------------------------------------------------
sub new {

   my ($pkg, $wide, $high, $char) = @_;

   my $r = {}; bless $r, $pkg;

   $r->{wide} = $wide;
   $r->{high} = $high;
   $r->{char} = $char;

   return $r;
}

#-----------------------------------------------------------
sub sortrecs {
   
   my ($rs) = @_;
   
   my @rs = sort {
               $b->{wide} * $b->{high} <=> $a->{wide} * $a->{high}
            } @{$rs};
   
   return \@rs;
}

#-----------------------------------------------------------
sub show {
   
   my ($r) = @_;
   
   print "$r->{wide} x $r->{high}\n";
   
   my $str = $r->{char} x $r->{wide};
   
   for (1..$r->{high}) { print "$str\n"; }
   
   print "\n";
}
[download]