Packaging Algorithm

Question

Good Day!

I'm trying to see if there is any way to accomplish this.

I've got a set of items, with associated attributes (Weight, Length, Width). I've also got a set of Packaging Types, with associated attributes (Max Weight, Length, Width)

I'm looking for an algorithm to determine the LEAST amount of boxes to package the items into.

So far, I've explored the knapsack problem, and although it can come close, I'm not exactly dealing with a weight, value type problem.

Here's an example:

Items: 10 x Item #1, (1lb each, 24" long, 12" wide) 5 x Item #2, (2lb each, 24" long, 6" wide)

Packaging Types: Small Box (MaxWeight = 40lbs, 24"x12") Large Box (MaxWeight = 75lbs, 24"x24")

The possible ways to package this would be: 2x Small Box -> One for each item type 1x Large Box -> Everything in it

I would want to return the single box result, although if I could return all possible combinations, that would also work.

Thanks in Advance!

Answer 1

You're describing bin packing. Note that this problem is NP-hard, so you won't get the optimal solution without a bruce force check. That said, there are algorithms that get you, IMO, a good enough answer.

Search around for descriptions of best fit decreasing and first fit decreasing.

Answer 2

Here's an interesting discussion of a 3D knapsack problem. Here's a paper on the same topic.

There was a similar discussion following a similar question.