关于打包箱子引发的思考

[0312birdzhang]

需求

如何用更少的箱子打包更多的小箱子，或者同样多的大箱子打包更多的小箱子。注意，小箱子有一种或多种，长宽高不完全一致，或者至少有一个边的边长不同。大箱子个数和尺寸同小箱子情况。

简单分析

这里面涉及到各种排列组合，每个小箱子的长宽高摆放都是一个新的排列，而且要合理的放入大箱子中，更充分的利用大箱子的空间。

理想中的实现

有这么一个 app ，可以添加大箱子的长宽高，可以有多种大箱子。然后添加要装入的小箱子长宽高，可以有多种。 然后 app 生成一种最合理的摆放的示意图，从下到上以 3d 展示。如果大箱子数量不够，可以给出提示。

箱子	尺寸(cm)	数量
大箱子 1	50x40x45	2
-	-	-
小箱子 1	20x10x6	5
小箱子 2	30x15x10	2

[beimenjun]

作为一个 App 开发者和一个搬家喜欢装箱子的来说一下。

你这个想法感觉是个很典型的算法题目啊。

但不管是商业上还是日常生活里，一般涉及到：在更大的箱子里装小箱子。感觉最佳实践都是优先使用统一的固定尺寸的小箱子，而且对这些箱子的置放方向与堆叠载荷都是有明确要求的。这种时候都不太需要用到 App 。

唯一能想到用途的就是快递企业了。

[lefthand2006]

可以做成一批货，一个集装箱，计算如何打包能装下最多货物

[coderluan]

这个叫集装箱问题，一般来说大学算法课最开始就是拿这个问题举例，用贪心算法先放大的后放小的。

[0312birdzhang]

@beimenjun 是的，一般都是标准的箱子，和产品配套的。

[kuanat]

可以参考这个装箱问题 wiki 上面 Bin_packing_problem

放到现实世界里，搬家这个场景一般都是一个固定大箱子，往里面放各种小箱子的问题。可能还会有更多约束，比如重量，一箱子书换谁都搬不动。所以人靠直觉一般能很快找到一个可行但不一定最优的方案，换作程序里可能就是经验或者启发式算法。

另外大箱子也是可以变形的，比如 50cm 长 30cm 宽，切割一下胶带一封就可以变成 40x40 或者 60x20 来用。

[0312birdzhang]

@coderluan @kuanat 感谢

[even77]

装箱问题，大学生数学建模比赛可能会遇到，之前本科的时候遇到过。但是到比赛的一半才意识到原题是这个问题😂，寄了。

[forty]

@kuanat 说的正是我想说的。

现实搬家场景来说，一般都是同样大小的纸箱，以及一些没放箱子里的东西，一股脑堆到货拉拉的货车里。
一般按照同类就装一起，宁可浪费点空间，不会为了稍微节省箱子而乱塞。先大后小一般没问题。

这个算法问题是很经典的，我在写 2D 自动布局的时候用过。