时间： 2016年7月
作者：竹林春雨
QQ:6996899
(一)前言
虽然辛勤务农多年，但在CSDN上上下下东西的情况也不少，一直没有做出任何贡献，突然觉得有点罪恶感。 最近，领导被指派设计仓库管理这样的软件。 其中有一部分涉及零售商仓库商品的包装出库，正好碰到商品的包装问题。 和大家分享想法，如果有不合适的地方，我想马上指出来，可以联系QQ或者直接留言。
)二)背景和业务描述
客户下单后，零售商仓库将商品打包出库仓库工作人员将下单购买的商品放入零售商提供的不同型号的箱子中，打包发送给客户。
客人点的东西里包含了各种大小规格的商品，有些东西不能翻倒。 玻璃瓶的饮料、易碎物品、带有重力传感器的仪器设备等不得倾倒。
供应商提供不同种类的箱型以方便商品的二次包装。
装箱工人需要根据情况把不同类型的商品放进合适的箱子里。
(三)叙述问题
首先，装箱工人需要对装箱过程中订购的商品选择箱型，评估商品体积与箱容积的准确比例，这一过程资源极其昂贵，给仓库工作带来困难，同时也降低了工作效率。
其次，送来的商品有时装箱不合理。 例如，顾客只是在买小商品，收到的确实是一个大空盒子，在浪费资源的同时，给用户带来了困惑，零售商的专业性也受到了质疑。
(四)制作目的和适用读者
这是为了帮助作者在实现算法的过程中思路清晰，不迷失方向。
(五) (需求)自己整理，如有偏差请谅解) ) )。
1 )自动计算某订单所需各种规格的箱子各有几个。
2 )商品不得倒置(翻转180度，上下倒置)。 但是，有些商品可以横着放。
3 )尽量不浪费箱子资源。 箱子尽量装满。
(六)定义
术语定义：
1、箱型：记录箱子型号、箱子内部空间纵横等属性。 箱型的高度，尤指箱子内部的高度。
2、普通箱型：最常用的箱子型号，符合大多数商品和便于携带的体积。
3、特型：是最不常用的箱型，不方便运输及码放。 例如，放晒衣竿的特长箱型、放大型冰箱的特大箱型。
4 )常规指数)箱型订单属性。 表示优先使用的箱子和不推荐的特型箱。 (数字越大越正常)
5 )容积)特别是箱子的容量。
6 )剩余容积)箱子放入一件商品后，还剩多少空间，箱子剩余的空间用几个结构化的更小的箱型表示。
7 )体积)特别是商品的体积。 (这里每个箱子只装一件商品，剩下的空间分割成更小的三个箱子) )。
8、满)如果箱子里装不下正在订购的其他商品，箱子的状态就是满的。
9、小于：如果箱子里可以放置订购中的其他任意小物品，箱子的状态小于。
10、爆箱)箱子还有一部分空间，但订单中最小的商品体积比箱子的剩余容积大。
11 )适合度)尤指一组商品和某种箱型的适合度，数值越小越适合。 拟合优度公式：0- (剩余容积-常规指数)得到的数字越大，拟合优度越高。
规则定义：
1 )所有箱子均为标准长方体或立方体。 纵横高度为内周的纵横高度(从箱子内部测量，从箱子外部测量时需要减去箱子壁的厚度)。
2 )所有商品均描述为矩形，长宽高为周边长宽高。
3 )装箱时，优先放置大件商品。 如果进不了大商品，就想想下一个小商品，等到装满为止。
4 )装箱时，优先选择容积小的箱子。 如果能把商品放进容积更小的箱子里，剩下的容积就会更小，说明箱子适合商品。 其次优先选择普通指数最大的箱子。 (值越大表示通常，值越小表示非通常箱型，甚至特型箱)
5 )如果订购的商品正好装完，箱子还没装满，就试着更换容积小的箱子。 如果有爆箱就放回原来的箱型。
6 )订购商品刚装箱，出现爆炸箱时，尝试更换hpdhm号箱，继续装箱剩余商品。 如果这个时候箱子已经是最小的话，就换成多个箱子装箱。
7 )将箱型按照适合度值从大到小的顺序排列。 箱子满的情况下，优先选择适合度值大的箱子。
8 )箱式按容积从小到大排列。 如果对箱子不满意的话，优先尝试小箱型。
9 )箱子优先放置大件商品，其次是大件商品，最后是订单中最小的商品。
10 )优先尝试用一个箱子完成一个订单的商品包装，然后尝试用多个箱子完成一个订单的商品包装。
11 )如果所有的箱子都不能把一个订单里的所有商品放在一个箱子里，只有启用多个箱子才能把商品放进去。 (个别特性箱可能只正对某个商品，在这种情况下，该箱型可以不参与该逻辑运算。 ) )
(七)数据模型
实体关系ER
实体列表
实体属性
订单
订单项目
商品
箱子
箱型
订单箱列表项目
客户
(七)实现过程
单个商品的一次性装箱过程
商品的长宽高以及箱子的长宽高分别如下图所示：
图一
单个商品装入箱子中以后如下图所示：
装进箱子中以后所产生的剩余空间如下图所示：
在商品可以装入箱子的情况下，每装入一次，可以产生三块新的空间，也就是新的箱子。三个新的箱子的大小是可以通过计算得到的。
假如上述方案，商品的长度、宽度或者高度中任意一个维度的值要大于箱子的长度、宽度或者高度的话，表示箱子装不下此商品，需要使用其它的摆放方案解决装箱问题。下文列出三种其它方案，加上上述方案，一共四种。
其它摆放方案
假设商品不可以倒置（其实商品在矩形形态下，倒置和正常放置占用空间一样，所以不考虑该情况），第二种方案是将上一种（前一章节的图三）横向旋转90度，假如横向旋转180度商品的占用空间和不旋转没有任何区别，所以该情况也不考虑，通过总结得出四种方案，以下将列出其余的三种方案。
第二种方案
将箱子内部的商品，在商品正常摆放（正面朝上）情况下，横向向右旋转90度得到下图的三个新的箱子（剩余空间）：
第三种方案
如果商品不介意放倒（平躺）的话，那么就会有第三种方案，在商品正常摆放（正面朝上）情况下，向左倾斜90度，得到如下三个剩余空间：
第四种方案
如果商品不介意放倒（平躺）的话，那么就会有第四种方案，在商品处于第三种方案摆放姿态的情况下，向右旋转90度，得到如下三个剩余空间：
(八) 小结
上述内容，对一次装箱过程进行了分解，每次需要一个商品和一个空箱子，同时会产生三块新的更小的剩余空间。这三块剩余空间又可以看作是新的箱子。和新的合适自己的空间大小的商品去匹配。
那么，这就是一个递归算法，方法输入一款商品和一个箱子，每一次递归都会产生三个新的箱子，新的箱子又可以装入其它更小的商品。
如此循环往复，直到每一个新的箱子连最小的商品都装不下了，或者没有任何商品可以装进箱子里了，这个过程就会自动结束。这是递归的出口条件。
其实，当然没有那么简单，图二所示的商品放入箱子的方法至少分为4种，每一种都需要尝试一下，以求得最合理的剩余空间；另外还有一订单多商品多箱子。
(九) 可能存在的问题
1， 箱子没有实际装满（”装满”的定义非本文中定义的）。
2， 用户会认为系统推荐的装箱方案不是太合理的安排。特型箱被匹配到常规商品上。例如：可能会有一种特别细长的箱型、而某种商品又恰好长宽都匹配，一字码放很多件后，刚好填满，这也是一个很奇葩的结局，需要特别考虑。
3， 部分箱型和商品需要手动匹配，因为某些箱子本来就是专门为指定的商品量身定做的。
(十) 尾声
程序员总是沉浸在自己的世界里、忽视身边的朋友、父母、妻子和孩子、最近南方洪灾不断、而执拗的老父刚刚负气而回、生活总有那么多的不如意。
如果此文还有一点价值的话，那就算是献给我需要感恩的人们吧…
作者在后来研发的新款WMS中就采用了该算法来计算和评估商品所需要的箱型。
代码请参考： http://smallcode.cn/post/4