Re: Packaging Algorithm
by mitd (Curate) on Nov 07, 2000 at 09:07 UTC

With all do respect to our esteemed monk extremely
is this not closer to the 'Knapsack' and 'bin packing'
class of problems which can be solved using several
nonbrute force techniques therefore do not fall into the general class
of NPComplete problems.
There are several books that cover detailed solutions to
these kinds of problems. My personal favourite is
'ALGORITHMS', Robert Sedgewick, AddisonWesley, 1983.
Sedgewick describes some excellent
approaches to your problem.
Computer Algorithms, Inroduction to Design and Analyssis,
Sara Base, AddisonWesley 1988 is also a good source.
mitdMade in the Dark
'My favourite colour appears to be grey.'  [reply] 

Actually, no it isn't like a binpacking problem. It's like
the spherepacking problem. It is unbounded since he specifically
asked for the smallest container. I'm pretty sure that is
a rather bit nastier than binpacking, since the only way to
find the answer is to run the binpacking 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)
 [reply] 

Why a sphere? He has a bunch of boxes. This seems perfect for a binpacking 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 predetermined discrete set of box sizes.
 [reply] 




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")
 [reply] 



Re: Packaging Algorithm
by extremely (Priest) on Nov 07, 2000 at 06:57 UTC

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 NPcomplete problems too but...)
I've not heard of anyone solving this or any related 2d
or 3d problem.
The balance problem, aka tapesides 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)  [reply] 

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 nontrivial 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."
 [reply] 

 [reply] 
RE: Packaging Algorithm
by marius (Hermit) on Nov 07, 2000 at 08:50 UTC

Incidentally, after much googling, I have found this which will almost cover what I'd like to do. After the suggestion of an IRC"pal" I decided to limit myself to boxes readily available at UHaul. The concept of limiting myself to purely integer units had already come to mind, and to come the number of "solutions" from being infinite, it's definitely needed. I'm not really looking for the definitive answer, just a good "guess" and close approximation. =]  [reply] 

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 rewriting this totally in Perl, but the algorithm is rather complex.
 [reply] 

Well, I've got the perl part down to picking the box that has the next highest capacity volume as the total volume of subboxes. (I'm using box information available at UHaul) Mind passing along the C algorithm?
 [reply] 

Re: Packaging Algorithm
by blogan (Monk) on Nov 07, 2000 at 08:41 UTC

I'm trying to think of an algorithm, and this is what I've gotten so far:
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();
 [reply] [d/l] 
RE: Packaging Algorithm
by Albannach (Monsignor) on Nov 07, 2000 at 19:07 UTC

I just wanted to mention that this just screams to me
for an adaptation of the Breeding Perls solution. If it weren't
for this darn job I'd probably obsess about it for days,
but since I haven't got the time now I'm throwing it in the
ring here in hopes that some enterprising and terminally (ha!)
bored student will have a go. C'mon, this is doctorate material!  [reply] 
Re: Packaging Algorithm
by Anonymous Monk on Feb 19, 2011 at 22:40 UTC

This is not a perl solution and doesn't offer source code but if you're keen on saving time and not reinventing the wheel, you can check out:
SolvingMaze
They have an eCommerce shipping calculator that packages items into multiple boxes of different sizes and returns the postage. It also supports items with multiple packaging dimensions or "thissideup" restriction, and boxes with postage varied by weight. There is an online API for integration with any application. As long your app has Internet connectivity, you can add to it.  [reply] 