Re: Rectangle packing...

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

I'll leave the ... as an exercise for others :))

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

Comment on Re: Rectangle packing... Download Code

Replies are listed 'Best First'.
Re: Re: Rectangle packing... by RMGir (Prior) on Apr 22, 2002 at 15:16 UTC
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	[reply]
Re: Re: Rectangle packing... by Anonymous Monk on Apr 23, 2002 at 01:32 UTC
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.	[reply]