找“最小包装尺寸的最优解“算法问题请教

gentlerain · 发表于 2019-6-20 15:30:23

一套产品有5种配件，每种配件个数不一（1~3个），总个数为11个。每个配件都已经用长方体盒子装好。
问题：应该如何放置，把这11个小盒子放进一个大的长方体盒子里（包装到一起），使得这个大盒子体积最小。

这个问题相信很多做产品的人都会遇到过。过去好像很多人都是自己拿到所有盒子自己随意叠放一下，自己认为是最优解了就定下来了。
现在我在想，有没有什么工具或者算法可以把这个最优解自动找出来的。因为这个问题每一次出产生都会遇到，而且是不同的尺寸和数量。
想过穷举法，但不知道怎么做这个算法，每个小盒子还能按不同的方向去放，组合很多很多啊。

wajlh · 发表于 2019-6-20 15:38:37

差不多就行，除非你们的产品要远走海外。

yj_yulin · 发表于 2019-6-20 15:39:10

这种问题应该是NP hard,没有太好的算法找最优解,基本上是随机或者基于一定规则找满意解.

dhbighead · 发表于 2019-6-20 15:39:29

本帖最后由 dhbighead 于 2019-6-20 15:42 编辑

三维的 binpack 问题
显然是NP-hard，写个ILP式子求一下就可以了。

随便找了个用excel求解的办法
https://bit.ly/2RpwFj1

gentlerain · 发表于 2019-6-20 17:58:28

dhbighead 发表于 2019-6-20 15:39
三维的 binpack 问题
显然是NP-hard，写个ILP式子求一下就可以了。

没梯子看不到

智涅 · 发表于 2019-6-20 18:18:08

感觉可以自己写个程序遍历一下

huangqi412 · 发表于 2019-6-20 20:47:34

呼叫豹警官

找“最小包装尺寸的最优解“算法问题请教

阿莫论坛20周年了！感谢大家的支持与爱护！！