关于打包箱子引发的思考

查看 46|回复 5
作者:0312birdzhang   
需求
如何用更少的箱子打包更多的小箱子,或者同样多的大箱子打包更多的小箱子。注意,小箱子有一种或多种,长宽高不完全一致,或者至少有一个边的边长不同。大箱子个数和尺寸同小箱子情况。
简单分析
这里面涉及到各种排列组合,每个小箱子的长宽高摆放都是一个新的排列,而且要合理的放入大箱子中,更充分的利用大箱子的空间。
理想中的实现
有这么一个 app ,可以添加大箱子的长宽高,可以有多种大箱子。然后添加要装入的小箱子长宽高,可以有多种。
然后 app 生成一种最合理的摆放的示意图,从下到上以 3d 展示。如果大箱子数量不够,可以给出提示。
[td]箱子[/td]
[td]尺寸(cm)[/td]
[td]数量[/td]
大箱子 1
50x40x45
2
-
-
-
小箱子 1
20x10x6
5
小箱子 2
30x15x10
2
beimenjun   
作为一个 App 开发者和一个搬家喜欢装箱子的来说一下。
你这个想法感觉是个很典型的算法题目啊。
但不管是商业上还是日常生活里,一般涉及到:在更大的箱子里装小箱子。感觉最佳实践都是优先使用统一的固定尺寸的小箱子,而且对这些箱子的置放方向与堆叠载荷都是有明确要求的。这种时候都不太需要用到 App 。
唯一能想到用途的就是快递企业了。
lefthand2006   
可以做成一批货,一个集装箱,计算如何打包能装下最多货物
coderluan   
这个叫集装箱问题,一般来说大学算法课最开始就是拿这个问题举例,用贪心算法先放大的后放小的。
0312birdzhang
OP
  
@beimenjun 是的,一般都是标准的箱子,和产品配套的。
kuanat   
可以参考这个装箱问题 wiki 上面 Bin_packing_problem
放到现实世界里,搬家这个场景一般都是一个固定大箱子,往里面放各种小箱子的问题。可能还会有更多约束,比如重量,一箱子书换谁都搬不动。所以人靠直觉一般能很快找到一个可行但不一定最优的方案,换作程序里可能就是经验或者启发式算法。
另外大箱子也是可以变形的,比如 50cm 长 30cm 宽,切割一下胶带一封就可以变成 40x40 或者 60x20 来用。
您需要登录后才可以回帖 登录 | 立即注册

返回顶部