php - 堆叠算法 - 在尽可能小的区域堆叠 3d 对象

Question

我正在尝试解决将对象堆叠成最方便邮寄尺寸的问题。物体的大小和形状会有所不同。所有对象的长度、宽度和高度都是已知的。

例如，客户可能会订购一个(长 x 宽 x 高)200x100x10 厘米的物体(宽、长和扁平)以及 2 个 50x50x50 厘米的物体(立方体)。如果我要打包这个，我会把扁平的宽物体放在底部，将 2 个立方体并排放在顶部。

有没有人拥有或知道对此有合理有效的算法解决方案？甚至是我应该考虑解决这个问题的方法。我整个星期都在编码，已经晚了，我的大脑被炸了。我还没有绝望，但我只想明天休息一天。

我设想的方式是创建一个表示 3d 空间的数组，每个数组元素表示该空间中的 1 平方/厘米。 3d 空间的长度和宽度将基于最长的对象和最宽的对象。然后你只需从最大的对象向下处理到最小的对象，找到足够的“洞”并边走边填满它们。

虽然我确信会有一个数学公式可以更有效地做到这一点。

有什么想法吗？

Answer 1

第一个建议——离开键盘，停止编码，开始思考!

第二条建议——您提出的方法(最大的优先，然后是次大的)是解决此问题的备受推崇和广泛使用的启发式方法。而且，除非你有大量的东西要打包，或者有大量的包装要做，否则不要太在意执行效率，开发效率应该是你的首要任务。

第三条建议 -- 谷歌关于装箱的信息，但要注意，有大量关于这方面的文献。

最后，不要那么肯定这有一个数学公式:-)