玩具箱挑战 - 电子商务发货/集装箱拆分 [英] Toy box challenge - E-commerce Shipment / Container splitting

问题描述

我正在寻找一种高效的 Ruby、JavaScript、Java 或 Python 实现，具有以下约束条件

我正在寻找一种有效的算法来正确识别存储项目列表所需的容器数量.上下文围绕为电子商务订单生成准确数量和类型的运输标签.

I'm looking for an efficient algorithm for correctly identifying the number of containers required to store a list of items. The context is around generating the accurate number and type of shipping labels for an e-commerce order.

给定:

• 物品具有已知的宽度、长度、深度和重量
• 物品具有包装类型，指定它们可以与同一容器中的其他物品组合(外包装")，或必须在自己的容器中运输(单独运输")
• 容器具有已知的宽度、长度、深度和承重能力
• 提供多种不同尺寸和容量的容器

问题:

• 存在物品清单，可能有不同的尺寸和包装类型，也可能有多种数量.拆分项目列表，以便将它们存储在尽可能少的容器中

我认为这是一个有趣的体积数学挑战，你们中的一些人可能会喜欢.我正在寻找解决此问题的最佳程序化解决方案.

I figure this is an interesting volumetric math challenge that a few of you might enjoy. I'm looking to figure out the best programmatic solution to this.

很高兴收到任何语言的解决方案，并且偏爱 Java、JavaScript、Python 或 Ruby.

Grateful to receive solutions in any language with a preference for Java, JavaScript, Python or Ruby.

提前致谢！

推荐答案

这正是 3D bin-packing问题.

单独运送"的要求只是通过将这些元素放在外面并单独运送它们而减少，这让您与其他人在一起.

The requirement of "ship alone" is simply reduced by putting these elements out and shipping them alone, which leaves you with the others.

找到最少数量的容器来包装它们现在是 3 维空间中的装箱问题.

Finding the minimal number of containers needed to pack them is now the bin-packing problem in 3 dimensional space.

这个问题显然是强 NP-Hard 问题，因此与背包不同 - 没有已知的伪多项式最优解.

This problem is undortunately Strongly NP-Hard, so unlike knapsack - there is no known pseudo polynomial optimal solution to it.

本文讨论的问题:三维装箱问题(Martello 等人)

这篇关于玩具箱挑战 - 电子商务发货/集装箱拆分的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！