Jerry Stuckle wrote:

I thought about it some more. And really, your problem isn't much

different than the historic traveling salesman (a salesman has to visit

X cities - what's the shortest distance he has to travel to visit all

cities). It's a great puzzle - and one which has never been solved

except by brute force, AFAIK.

And I think that's what you're going to have to do here, unfortunately.

If you want to get the *best* possible packaging solution, then like

you say, there's just no way around it...you're going to have to expand

the entire search tree. But, if you could be satisfied with the best

solution chosen from a subset of all solutions, then a

heuristic-directed A* search could be a good candidate.

Without delving deeper into the problem, a good starting heurstic would

simply be the amount of empty space left in the package. Keep

expanding the tree and following the branch dictated by the heuristic

until you get to a point where you can fit no more packages, and

declare that a possible solution. Backtrack out of the solution (how

far to back out will depend upon how similar you want your solution

subset to be...further = a more diverse set). Repeat X times to get

however many possible solutions you want to have, then choose the best

one as your actual packaging setup.

As I said, if you don't need the actual best solution, but only a

*good* solution, then this approach would save you processing time and

memory because you don't have to examine all possible options, just the

most promising ones.