分享兴趣，传播快乐，增长见闻，留下美好！

亲爱的您，这里是Learning Yard学苑。

今天大亭为大家带来我的“三维装箱问题及关键点装箱算法”，欢迎您的访问。

Share interest，spread happiness ，

increase knowledge and leave beautiful.

Dear you，this is the Learing Yard Academy!

Today, Dating will brings you “3d packing problem and key point packing algorithm”，

Welcome your visit!

一、三维装箱问题

三维装箱问题（NP-Complete）即研究如何用最少数量的箱子将物品装起来。本质上是离散组合最优化问题。此类问题目前并没有任何算法能够在多项式时间内解得答案。意味着对于此类问题，一般只能采用诸如暴力解等时间复杂度很高的算法求解。当物品数n和容器数量k增加时，求得最优解所需时间也会急剧增长。想要减短计算时间，可以使用启发式算法计算。

Three dimensional packing problem (NP Complete) is to study how to use the minimum number of boxes to pack items. Essentially, it is a discrete combinatorial optimization problem. At present, no algorithm can solve such problems in polynomial time. It means that such problems can only be solved by algorithms with high time complexity, such as brute force solution. When the number of items n and the number of containers k increase, the time required to obtain the optimal solution will also increase rapidly. If you want to reduce the calculation time, you can use a heuristic algorithm to calculate.

二、关键点装箱算法

关键点法在解决二维装箱问题中十分常见，而针对三维装箱问题，我们可以采用类比的思想。其中心思想都是尽可能想把物品往箱子底边的顶点靠近，对于规则的物品，将其整齐摆放使彼此接触面积最大化。此时每增加一个并重叠摆放在箱子中便增加7个关键点。但是关键点装箱算法也有明显的局限性。我个人认为关键点法只能解决近似于规则物体的装箱问题。例如盒子，拥有长方体的表面, 且无弹性. 用长宽高来描述盒子的尺寸；又或者袋子， 它其实也是高度为零的长方体表面. 用长和宽描述袋子的尺寸. 柔软且富有弹性。换句话说它可以变形成盒子。对于当前绿色物流的要求，我们并不鼓励盒子套盒子的打包方法，而若想使用关键点法对于不规则物品，就得先对其形状规则化。因此我认为通过本算法虽然能够获得一个较有策略的装箱结果，但从算法步骤和优化策略上看还有较大发展空间。

The key point method is very common in solving two-dimensional packing problems, while for three-dimensional packing problems, we can use the idea of analogy. The central idea is to try to get the items close to the top of the bottom edge of the box as much as possible. For regular items, place them neatly to maximize the contact area. At this time, 7 key points will be added for each additional key point placed in the box. But the key point packing algorithm also has obvious limitations. Personally, I think the key point method can only solve the problem of packing objects that are similar to regular objects. For example, a box has the surface of a box and is inelastic Use length, width and height to describe the size of the box; Or a bag, which is actually a cuboid surface with zero height Describe the size of the bag in terms of length and width Soft and elastic. In other words, it can become a box. As for the current requirements of green logistics, we do not encourage the packaging method of "box in box". If you want to use the key point method for irregular items, you must first regularize their shapes. Therefore, I believe that although this algorithm can obtain a more strategic packing result, there is still much room for development in terms of algorithm steps and optimization strategies.

今天的分享就到这里了，

如果您对文章有独特的想法，欢迎给我们留言。

让我们相约明天，祝您今天过得开心快乐！

That's it for today's sharing. If you have a unique idea about the article.please leave us a message.Let us meet tomorrow I wish you a happy day today!

参考资料：百度、中国知网

翻译来源：百度翻译

声明：本文由LearningYard新学苑原创，如有侵权，请联系删除！

文案|雷雅婷

排版|雷雅婷

审核|闫庆红