Algorithm for distribute products to boxes

Question

I have Products and Boxes. I want to use minimum box count for packaging. Please ignore product and box dimensions (WxHxD). Only focus on volumes.

I need an algorithm for placing these products to boxes. Algorithm must use minimum count of boxes and the smallest boxes it can. Algorithm can use same box more than one. Each product can be used only one time.

I Tried this algorithm

• Order products ascending by volume
• Put smallest product to biggest box, then add next product to box. Until there is no space for next one. Repeat until products finish.

Acoording to this algorithm

• E product to Z-1 Box (Free Space: 2900 cm3)
• B product to Z-1 Box (Free Space: 2700 cm3)
• F product to Z-1 Box (Free Space: 2300 cm3)
• D product to Z-1 Box (Free Space: 1700 cm3)
• A product to Z-1 Box (Free Space: 700 cm3)
• B product to Z-2 Box (Free Space: 1500 cm3)

---

So algorithm uses 2 pieces Z Box. But human brain can fit (C+A+F+E)= 3000 cm3 (Z box) and (B+D) = 800 cm3 (X Box) Thanks for all comments and replies.

Answer 1

I would calculate the optimal ways to fit the boxes inside each other.

• One Z equals one V and one X.
• One V equals two X.
• One X equals two U.
• One U equals up to five T (must be able to combine at least 2 boxes into 1 for any box merge to make sense).

This step may be rather computationally expensive depending on how many boxes you have and how easily you get fit them into each other. IE: This would be much less straightforward and harder if you had box size where they are no common multiples. See the https://en.wikipedia.org/wiki/Change-making_problem for examples of what really "nice" box size combinations would look like (the example you gave is quite nice).

Move all products in one box to other boxes with the goal of get as close to 0 remaining space as you can, ideally start by looking for moves that result in exactly 0 remaining space (only by taking everything in one box and moving it to another box).

Then merge the boxes as much as you can on the above rules as long as it reduces the # of boxes by at least one. IE: CEF=> V (technically it would be E => F, then EF => C), A => X, DB => X. Then you can combine it from there. ADB = V (Combine 2X boxes into a single V box).

Another valid option is: DF => X, BCE => V, A => X. In this case, we still combine the two X into a V. There are also likely solutions where you might have 1 V and 1 Z, but that only makes sense if you had 1X and 1V, otherwise it would be better to use 2X => 1V instead.