2

我们说的是金属制品厂。有机器将长铁条切割成更小的部分，后来用于制造各种产品。

例如，我要求生产以下长度和数量的棒材：2 根 248 毫米，5 根 1150 毫米，6 根 2843 毫米，3 根 3621 毫米。

那是分区输出。

在输入端，我有（再次举例）3 条 2500 毫米、2 条 5000 毫米、6 条 8000 毫米和 3 条 10000 毫米的条。

我应该找到一种如何以最佳方式切割输入条的方法 - 切割后的其余部分（剩余部分太小而无法使用）应该尽可能小。

我创建了一种算法，它简单地创建所有可能的组合，然后从中挑选出最好的一种。代码可以工作，但是只要输入和输出稍微大一点，计算就会持续很长时间，所以我必须找到解决问题的新方法。

你有什么提示吗？

4

4 回答 4

5

您的问题是运筹学中很常见的问题。看看 切割库存问题。正如您自己发现的那样，这个问题本质上是 NP-hard。它不能很好地扩展。

如何解决？在您能够弄清楚模型之后，最好调用一些混合整数规划求解器。我以前使用过LPSolve 5.5

可能有更简单的算法，您可以编写特别处理这个问题的代码。当您需要添加一些作者没有想到的侧面约束时，通常会出现这些算法的问题。MIP Solver 是一种更通用的工具。

于 2009-09-10T15:16:52.420 回答
4

这称为可变尺寸装箱问题。这是 NP 难，这意味着您的解决方案总是会因大量输入而失败。这篇文章，在这里，不幸的是我也没有访问权限，它解决了这个问题，并以金属切削行业为例。

于 2009-09-10T15:14:41.787 回答
1

线性规划是你的朋友。一般见http://en.wikipedia.org/wiki/Linear_programming，特别是http://en.wikipedia.org/wiki/Linear_programming#Uses , http://en.wikipedia.org/wiki/Linear_programming #算法。

于 2009-09-10T15:12:06.470 回答
1

看起来它类似于背包问题（知道真的很讨厌）我在 NIST DADS（方便参考）上发现这个比非会员的 ACM 更容易获得Bin Packing

于 2009-09-10T15:16:30.093 回答