0

我已经按照所需的顺序订购了一个拣货清单（要在仓库中拣货的物品清单）。每个项目都有宽度、长度和高度。当我首先报告一个拣货清单时，我必须选择一个包裹以便将这些物品放在某个地方。包装也有宽度、长度和高度（假设填充率=100%）。领料单上的项目数量只能被整数整除。要回答的问题是；如果我想尽量减少包的数量，我应该使用多少个包？我如何知道包裹顺序？（所以我知道每次开始报告拣货清单或开始新包裹时要拣货的包裹？

对我来说，这些是一些变量和固定数字。

Item    FIXED
Item Quantity   FIXED
Item Width  FIXED
Item Lenght FIXED
Item Height FIXED
Item volume FIXED
Package VARIABLE
Package Quantity    VARIABLE
Package Width   FIXED
Package Lenght  FIXED
Package Height  FIXED
Package Volume  FIXED
Package fill rate   FIXED
Package sequence    VARIABLE

有谁能解决吗？

4

1 回答 1

0

这是一个被称为装箱问题的一般问题。它有很多解决方案，但总的来说是一个NP-hard 问题，这意味着没有多项式解决方案。此外，您可能无法 100% 装满包裹。

大多数算法都尝试使用启发式算法而不是找到最佳解决方案，而是寻找最快的解决方案。这些是贪心算法，并产生适度有效的结果（例如，如果有剩余物品，则没有盒子会保持少于一半的空）。

一本名为《算法设计手册》的书就这个问题写了以下内容：

分析和实证结果表明，“首次拟合递减”是最好的启发式方法。按大小递减的顺序对对象进行排序，使最大的对象在前，最小的在后。将每个对象一个接一个地插入第一个有空间的容器中。

于 2018-01-12T19:03:01.047 回答