用于分发片段的算法

Question

嗨,我正在为一家以这种方式运作的制造公司工作

我们得到特定尺寸的材料卷,我们的供应商可以说每卷8000米.然后我们从2000米,3000米等小尺寸的不同客户处获得订单.我想知道如何创建一个软件,他们只需输入他们当前的卷尺和我们现在拥有的不同订单.生成切割不同卷的最佳方法,以尽量减少浪费.

例如,在特定时间点我们可能有以下订单:2件3000米2件4000米6件1500米

然后我们应该输入的是上面的订单以及供应商为我们提供的卷尺寸我们假设它是8000米.

然后软件应该生成输出,例如Roll 1 - 两件4000米Roll Wasted 0 Roll 2 - 两件3000米和1件1500(Roll Wasted 500)Roll 3 - 五件15000(Roll Wasted 500)

应该优化脚本,因为上面的例子非常小.通常情况下,我们一次会订购约200件

我正在考虑在PHP和MYSQL中这样做,因此它可以基于Web,公司周围的人可以使用它.

我知道我们可以通过蛮力尝试每种组合来做到这一点.但在这种情况下是否还有其他排序算法和技术可以提供帮助.

Answer 1

您正在寻找一维装箱算法。解决这个问题的策略有很多种：First-Fit、Best-Fit、Random-Fit。我在 phpclasses.org 上编写了一个 php 解决方案。你可以免费下载我的程序（打包）。事实上我已经因此获奖了。如果你的问题不是那么大，我会尝试暴力方法。