From: Bill Guindon Date: 2005-06-30T06:49:42+09:00 Subject: Re: Programmers Contest: Fit pictures on a page On 6/29/05, Michael Campbell wrote: > On 6/29/05, Phrogz wrote: > > > Karl, I think you are (incorrectly) assuming that all the pictures have > > the same size or aspect ratio. It's a bin-packing problem. Given a > > fixed-size space and differing-sized objects, the ways in which they > > are placed very much affect the amount of leftover space. > > How so? Given that any suitable, rule-conforming arrangement of > objects has them all inside the bin, no overlapping, etc., the volume > of the bin - the sum of the volume of the objects = leftover volume; > how they are placed nor how they are shaped has any bearing on the > problem. It SOUNDS like the OP is trying to maximize the > "contiguousness" of the leftover space, but that's not how it reads. > Not even sure how you'd measure that; minimize the magnitude of the of > the length of the perimiter? Yeah, I read it as maximizing the remaining "usable" space - but I don't see how you would define that either. > Is the problem then to see HOW one might place 'n' rectangular shapes > inside a rectangular boundry such that none of the placed shapes > overlap each other, nor exceed the perimeter of the boundry? Well, there was the clause "up to 26 pictures", so possibly it's a comparison of algorithms based on how many of the 26 you could fit. If their total area is larger than the sheets total area, then it would get interesting. > Or is it possibly, what's the minimum number of (uniformly > dimensioned?) boundries required to FIT the n shapes? THIS sort of > problem is one I come across regularly in woodworking; how do I > minimize the number of sheets of plywood (etc.) needed to cut out all > the pieces of a given construction? Used to love reading the pop-sci plywood contests. Watching people build spiral staircases out of 4 sheets of plywood and other silliness. good stuff :) -- Bill Guindon (aka aGorilla)