产业划分问题
我们说的是金属制品厂。有一种机器可以将长长的铁棒切割成较小的部分，然后用来制造各种产品。
例如，我需要生产长度和数量如下的棒材:2块248 to，5块110 to，6块2843 to，3块3621 to。
这就是分区输出。
在输入端，我有(再次举个例子)3根2500 of的棒，2根5000 of的棒，6根8000 of的棒和3根10000 of的棒。
我应该找到一种方法来最优地剪切输入栏-剪切后的其余部分(太小而不能使用的剩余部分)应该尽可能小。
我已经创建了一个算法，它可以简单地创建所有可能的组合，然后从中挑选最好的一个。代码可以工作，但是一旦输入和输出稍微大一点，计算就会持续很长时间，所以我必须找到解决问题的新方法。
你有什么提示吗？
回答 4
Stack Overflow用户
发布于 2009-09-10 15:16:52
你的问题在运筹学中是很常见的问题。看看Cutting stock problem吧。这个问题本质上是NP难的，因为你已经自己弄明白了。它的可扩展性不是很好。
如何解决？在您能够弄清楚模型之后，最好调用一些混合整数编程求解器。我以前使用过LPSolve 5.5
可能有更简单的算法，你可以编写代码来特别处理这个问题。这些算法的问题通常出现在您需要添加作者没有考虑到的一些副作用约束时。MIP解算器是更通用的工具。
Stack Overflow用户
发布于 2009-09-10 15:14:42
这就是所谓的可变尺寸装箱问题。它是NP困难的，这意味着你的解决方案对于大输入总是失败的。不幸的是，这篇名为here的文章解决了这个问题，并以金属切削行业为例。
Stack Overflow用户
发布于 2009-09-10 15:12:06
线性编程是你的朋友。请参阅http://en.wikipedia.org/wiki/Linear_programming的一般内容，特别是http://en.wikipedia.org/wiki/Linear_programming#Uses和http://en.wikipedia.org/wiki/Linear_programming#Algorithms。
https://stackoverflow.com/questions/1405837
复制相似问题
腾讯云开发者
