产业分区问题
我们说的是金属制品厂。有一台机器可以将长铁条切割成较小的零件，然后用于制造各种产品。
例如，我需要生产以下长度和数量的棒材： 2片248mm， 5个1150mm， 6 2843mm， 3 个 3621 毫米。
这就是分区输出。
在输入端我有（再次举例） 3根2500mm的钢筋， 2根5000mm的棒材， 6根8000mm的棒材 和 3 根 10000mm 的钢筋。
我应该找到一种最佳方式切割输入条的方法 - 切割后的其余部分（剩余的太小而无法使用的部分）应该尽可能最小。
我创建了一种算法，它可以简单地创建所有可能的组合，然后选择其中最好的一个。代码可以工作，但是一旦输入和输出稍微大一点，计算就会持续很长时间，所以我必须找到解决问题的新方法。
你有什么提示吗？
We're talking about metal products factory. There is machine which cuts long iron bars to smaller parts which are later used for creating various products.
For example, I have requirement to produce bars of following length and quantity:
2 pieces of 248mm,
5 of 1150mm,
6 of 2843mm,
3 of 3621mm.
That is the partitioning output.
On input side I have (again for example)
3 bars of 2500mm,
2 bars of 5000mm,
6 bars of 8000mm
and 3 bars of 10000mm.
I should find a way how to cut input bars optimally - the rest (remaining parts that are too small to be used) after cutting should be smallest as possible.
I've created algorithm which simply creates all possible combinations and then pick best one among them. Code works, but as soon as input and output are little bit bigger, calculation can last very long, so I must find new approach to the problem.
Do you have any hints?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
你的问题是运筹学中很常见的问题。看看
切割库存问题。这个问题本质上是 NP 难问题，正如您自己发现的那样。它的扩展性不太好。
怎么解决呢？在您能够计算出模型后，最好调用一些混合整数规划求解器。我以前使用过 LPSolve 5.5
您可能可以编写更简单的算法来处理此问题特别的。当您需要添加一些作者没有想到的附加约束时，这些算法通常会出现问题。 MIP 求解器是更通用的工具。
Your problem is quite common problem in Operations Research. Look at
Cutting stock problem. This problem is essentially NP-hard as you have figured out on your own. It doesn't scale very well.
How to solve it ? After you are able to figure out the model it would be best to call some mixed integer programming solver. I have previously used LPSolve 5.5
There may be simplier algorithms that you could code that deal with this problem in particular. The problem with these algorithms usually arises when you need to add some side constraints that the authors haven't thought of. The MIP Solver is way more generic tool.
这称为可变尺寸装箱问题。它是 NP 困难的，这意味着您的解决方案对于大输入总是会失败。这篇文章，此处，不幸的是我也没有访问权限，地址这个问题并以金属切削行业为例。
This is called the variable size bin packing problem. It's NP hard, which means that your solution will invariably fail for large input. This article, here, which unfortunately I don't have access too, addresses this problem and uses the metal cutting industry as an example.
线性规划是你的朋友。一般情况请参阅 http://en.wikipedia.org/wiki/Linear_programming，特别是, http://en.wikipedia.org/wiki/Linear_programming#Uses, < a href="http://en.wikipedia.org/wiki/Linear_programming#Algorithms" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Linear_programming#Algorithms。
Linear programming is your friend. See http://en.wikipedia.org/wiki/Linear_programming in general, and, particulary, http://en.wikipedia.org/wiki/Linear_programming#Uses, http://en.wikipedia.org/wiki/Linear_programming#Algorithms.
看起来它与背包问题类似（知道这真的很令人讨厌），我在 NIST DADS（方便的参考）上发现这个问题比非会员的 ACM 更容易找到装箱
Looks like it's similar to the knapsack problem (know to be really nasty) I found this on the NIST DADS (handy reference) easier to get to than ACM for non members Bin Packing