algorithm - 剪裁 pipe 时如何计算最小浪费

Question

我有一个相当数学的问题需要解决:

任务是用最少的废料从固定长度的管中切割出预定数量的管。

假设我想从标准长度为 6m 的 pipe 中切割出 10 根 1m 的 pipe 和 20 根 2.5m 的 pipe 。

我不确定这种问题的算法是什么样的？

我想创建一个不同尺寸 pipe 的变体列表，将它们装入标准尺寸的 pipe 中，然后然后选择浪费最少的变体。

首先我不确定是否有其他更好的方法来解决这个问题。

其次，我没有找到如何创建这样一个变体列表的解决方案。

非常感谢任何帮助，谢谢!

Answer 1

我相信您描述的是 cutting stock problem .可以找到一些附加信息 here .