物流公司在流通过程中,需要将打包完毕的箱子装入到一个货车的车厢中,为了提高物流效率,需要将车厢尽量填满,显然,车厢如果能被100%填满是最优的,但通常认为,车厢能够填满85%,可认为装箱是比较优化的。 设车厢为长方形,其长宽高分别为L,W,H;共有n个箱子,箱子也为长方形,第i个箱子的长宽高为li,wi,hi(n个箱子的体积总和是要远远大于车厢的体积),做以下假设和要求:
- 长方形的车厢共有8个角,并设靠近驾驶室并位于下端的一个角的坐标为(0,0,0),车厢共6个面,其中长的4个面,以及靠近驾驶室的面是封闭的,只有一个面是开着的,用于工人搬运箱子;
- 需要计算出每个箱子在车厢中的坐标,即每个箱子摆放后,其和车厢坐标为(0,0,0)的角相对应的角在车厢中的坐标,并计算车厢的填充率。 问题分解为基础和高级部分,完成基础部分可得78分以上,完成高级部分可得85分以上。
所有的参数为整数;2. 静态装箱,即从n个箱子中选取m个箱子,并实现m个箱子在车厢中的摆放(无需考虑装箱的顺序,即不需要考虑箱子从内向外,从下向上这种在车厢中的装箱顺序);3. 所有的箱子全部平放,即箱子的最大面朝下摆放;4. 算法时间不做严格要求,只要1天内得出结果都可。
参数考虑小数点后两位;2. 实现在线算法,也就是箱子是按照随机顺序到达,先到达先摆放;3. 需要考虑箱子的摆放顺序,即箱子是从内到外,从下向上的摆放顺序;4. 因箱子共有3个不同的面,所有每个箱子有6种不同的摆放状态(每个面可以横着摆或竖着摆);5. 算法需要实时得出结果,即算法时间小于等于2秒。