I've not heard of anyone solving this or any related 2d or 3d problem.

The balance problem, aka tape-sides is a good simpler example. Given a set of weights (or a set of song lengths) divide them into two sets that have the least difference in weight (length)

There are a lot of nice strategies but they all have nasty cases that don't work. Exaustively trying every case is the only hope. The best bet is to minimize the cases you have to exhaust. Force everything to inch(cm) boundries, move boxes on the same. Pack things around the largest volume item, etc.

Really, not to discourage you too much, it might be a good idea to start on something a bit simpler, like curing cancer. =)

--
$you = new YOU;
honk() if $you->love(perl)

Remember, just because a problem is NP, doesn't mean it's unsolvable. It just means that there's no (known) way to solve it in polynomial time. All we can do in polynomial time is verify a solution.

There's no reason that one couldn't write an algorithm to solve this problem. The problem is that for any non-trivial number of boxes, it would take a long, long time and/or some pretty expensive hardware to run that algorithm.

--
Ryan Koppenhaver, Aspiring Perl Hacker
"I ask for so little. Just fear me, love me, do as I say and I will be your slave."

There isn't an answer to this one. There are some strategies for doing this with restrained box sizes but the general case you describe isn't actually solvable. At least no one has yet. (of course, there may be some genius out there that just broke NP-complete problems too but...)

Actually, I was playing Minesweeper this morning... awww nevermind.

ALL HAIL BRAK!!!

There are several books that cover detailed solutions to these kinds of problems. My personal favourite is 'ALGORITHMS', Robert Sedgewick, Addison-Wesley, 1983.

Sedgewick describes some excellent approaches to your problem.

Computer Algorithms, Inroduction to Design and Analyssis, Sara Base, Addison-Wesley 1988 is also a good source.

mitd-Made in the Dark
'My favourite colour appears to be grey.'

Actually, no it isn't like a bin-packing problem. It's like the sphere-packing problem. It is unbounded since he specifically asked for the smallest container. I'm pretty sure that is a rather bit nastier than bin-packing, since the only way to find the answer is to run the bin-packing work on a huge series of various container sizes. As I recall, that was what made this such a nasty problem, there isn't a specific strategy for finding the "best" answer, just a good strategy for finding a "fair" answer for a single facet of the problem.

OTOH, mentioning Sedgewick's book is good enough for a ++ in my book, anyday =) And you are correct in that refactoring the problem can surely help make it solvable.

--
$you = new YOU;
honk() if $you->love(perl)

Why a sphere? He has a bunch of boxes. This seems perfect for a bin-packing problem. He just needs to try the algorithm against successively larger containers until he's able to fit everything. He's followed up with a comment indicating that he's already planned to limit himself to a pre-determined discrete set of box sizes.

BTW, I used to work for a guy who had several good solutions for packing spheres. He used them for designing composites (for example, what mixes of sizes of gravel to use for certain types of concrete). One involved selecting spheres from the chosen mix at random and dropping them into a virtual cylinder and letting them settle. Sure, he wasn't proving the maximally tightest possible packing. But he was able to make good predictions about how certain mixes of sizes of spheres would pack in practice.

He also sometimes repeated the experiment of make a bunch of spheres, put them in a bag, squeeze the bag for a few days, poor wax in, let it cool, remove bag, analyze positions of spheres.

Don't let someone's proof that some problem is impossible to solve prevent you from solving the problem well enough to get your work done!

        - tye (but my friends call me "Tye")

foreach (@closefamilymember) {
  $gift = perfectgift $_;
  buy($gift);
  push @boughtengifts, $gift;
}
foreach (@boughtengifts) {
  $box->pack($_);
}

foreach (@notsoclosemember) {
  $gift = perfectgift $_;
  if (!box->pack($gift)) {
      $gift = giftthatwillfitinfreespace $_;
      $box->pack($gift);
  }
}

box->mail();
[download]

I've found a similar algorithm, written in C. This is giving me an excuse to play with the Inline module, but I won't have anything tonight. :)

But yah the algorithm calls for a known container size, and it attempts to pack everything into that container. What I'd like to do is extend this C version using Perl to give us the needed "given these sizes, what's the smallest that successfully packs everything" behavior, which would just iterate from the smallest to the largest (or whatever order, since I guess some boxes of the same size might be cheaper than others, etc.), and return the first one that gets them all in.

I thought about re-writing this totally in Perl, but the algorithm is rather complex.

Well, I've got the perl part down to picking the box that has the next highest capacity volume as the total volume of sub-boxes. (I'm using box information available at U-Haul) Mind passing along the C algorithm?

SolvingMaze