strikernl - 4 months ago 41

PHP Question

I am creating a shipping module for a custom webshop (in PHP) that is turning out to be a bit complex (for me anyway);

in the desired shipping procedure, there are (currently) two outer 'shipping boxes/containers' that can each contain a different combination of items/products. There is a big one and a small one, and the small one is obviously cheaper to ship. Items/product (currently) fall into three dimensions of 'inner boxes'.

I am looking for an API/class in which I can input the dimensions of the outer boxes, then the amounts and dimensions of inner boxes (or rather, products) to be shipped. The optimal combination of outer boxes and its contents/packing order should then be calculated, such that the smallest amount of boxes is needed.

Needless to say, I expect the number of outer boxes, inner boxes and their dimensions are probably very likely to change in the future.

Does this even exist?

Answer

This is an instance of the famous Packing problem, most of which is NP-hard. To find an optimal solution to such problems may be very hard or impossible, so you should aim for a *good enough* solution rather than the *optimal* one.

You should check out the Bin packing problem which is very similar to your problem, with the difference that you have two different volumes for the bins.