管材切割优化算法

Question

我面临的问题是找到一种算法来优化将一段管道切割成更小、不同长度的管道。例如，您有10米长的标准管道，您需要切割以下部分: 0.7米的4个部分，2.1米的3个部分，5米的7个部分等等。目标是保持切割的最佳顺序，以便将浪费保持在最低限度。

我有一个解决方案，但我不确定它是不是最好的。首先，我创建了一个包含所有长度的堆栈(stack1)，按大小排序，较大的值在顶部。我定义了一个空的辅助堆栈，stack2数组管道存储结果。N是管道编号，m是要从该管道剪切的长度。然后我执行以下步骤(这是伪代码)：

i=0
j=0
while(stack1 in not empty or stack2 is not empty)
    a=pop(stack1)
    if(a==null)
        push(stack2,stack1) ;push stack2 into stack1
        sort(stack1)
        i=i+1
        j=0
        a=pop(stack1)
    if(a fits in pipe[i])
        pipe[i][j++]=a   ;this just means that 'a' will be cut from this pipe
    else
        push(a,stack2)   ;if it doesnt fit, save it for later

总而言之:它总是试图尽可能地减少请求的最大部分。当它不能时，它转到下一项，依此类推。当它用完了可以尝试的项目时，它会从一个新的“原始”标准长度的管道开始。

这似乎是有效的，但我想知道它是否可以改进。有没有办法确定最好的解决方案是什么？

Answer 1

这就是下料问题。正如user3386109所指出的，您的算法不会产生最佳解决方案。这也是NP困难的，因为装箱可以简化为削减库存。

例如，假设您的管道长度为100，需要切割4个34长度的管道和8个33长度的管道，这说明您的算法不是最优的。正确的做法是把三根管子切成两根33和一根34。然而，您的第一次拟合方法将把两个管道切割成两个34，将两个管道切割成三个33，并将一个管道切割成两个33。

如果没有太多有效的方法来切割管道(比如，至多几千种)，您可以枚举所有这些方法，这样就得到了一个通常不太难解决的不等式背包问题。如果有更有用的方法来切割管道，有一种著名的列生成方法，这是由Gilmore和Gomory提出的，它在实践中很有用。