计算最有效分组的算法

Question

我有一个很奇怪的问题。

我有一个不同尺寸的木梁长度列表(约 500 个条目)，例如 3400 毫米、1245 毫米、900 毫米等。木梁的最大长度为 5400 毫米，为了减少木材的浪费量，我想找到一种算法，尝试各种可能的方法来组合较小的尺寸以适应 5400 毫米的梁或尽可能接近。

假设我有五种不同的长度:3000、1000、300、2000、900 我最终会得到:

• 3000+2000+300 = 5300//最接近 5400 的组合，这意味着该梁上浪费的木材量仅为 100 毫米。

• 1000+900 = 1900//剩下的

我不确定这是否符合旅行商问题的条件，而且我才刚刚开始想象该算法可能是什么样子。但是因为这里有这么多聪明人具有组合技能，所以我只想在我把头撞得血淋淋之前把它扔出去。

让事情变得更糟

假设我们确实找到了上述问题的解决方案。木工店的人很少提供 5400 毫米的光束，但它可以以 100 毫米的间隔从 3000 到 5000 不等。所以我会在交货时从他们那里得到一份光束长度列表。

是否可以将列表“这是我得到的光束”与列表“找出所需光束长度的最佳组合”相匹配？

我不确定这最终是否值得，但感谢任何帮助。

亲切的问候理查德

Answer 1

这是 Cutting Stock Problem在一维。它可以简化为 Knapsack problem所以它实际上是 NP 完全的，但它通常很容易处理，并且在不存在很多好的近似解决方案的情况下，因为这是工业中一个非常重要的问题。

它通常使用动态规划来精确解决，这有点费脑筋，但您可以找到大量示例实现来帮助您解决问题。近似多项式时间解决方案通常在各个点调用动态规划代码(具有伪多项式复杂度)，并且周围代码更简单。我想这里的要点是不要尝试自己编写，找到别人的代码并将其移植到您的语言和应用程序环境中。