将板安装到可用长度的算法，最大限度地减少浪费

Question

我正在编写一个在木材场使用的应用程序。给定一定数量的板或梁长度，目标是计算所需的板数量，同时最大限度地减少浪费。例如，对于某一特定维度，可能有以下购物清单：

3x 2.9 米
5x 1.6 米
21x 0.9 米

在木材场，人们会检查可用的木板长度并将其输入应用程序。假设此尺寸有 4.8 米长。

一个简单的方法是尝试以降序安装剩余的板：

2.9 + 2.9 = 5.8 所以这不适合 4.8 米的板子
2.9 + 1.6 = 4.5 所以没关系。

任何长度都不小于剩余的 0.3 米，所以这块板是“满的”。我们将再安装两个这种类型，然后我们还有以下长度可以安装：

2x 1.6 米
21x 0.9 米

好的，所以这个算法运行得相当好。但是，如果我们不是拟合 2.9 + 1.6，而是拟合 2.9 + 0.9 + 0.9 = 4.7 呢？然后我们将每块板浪费 0.1 米，而不是 0.3 米。

枚举所有可能的组合的一个问题是，每个长度在一块板上可能出现不止一次，并且板上适合的长度数量也会有所不同。是否有一种已知的算法可以用来最大限度地减少所有电路板的总浪费？

此外，如果木材场有两种或更多长度可用怎么办？例如 5.4、4.8 和 3.6 米？这肯定会使事情复杂化。可以为每个可用长度运行选定的算法，并选择浪费最少的长度。但最优雅的解决方案是允许混合可用长度，因此最佳答案可能是 1x 5.4、3x 4.8、6x 3.6。但是对于初学者来说，我很乐意将答案限制为一个长度。

Answer 1

您的特定问题是所谓的“切割库存”类问题的变体。看看维基百科的“切削库存问题”（CSP）页面

我喜欢用简单的英语对下料问题的简单版本进行解释。来自AIMMS：

“切割库存问题：在给定每个成品的需求的情况下，如何将长卷材料（称为原材料）切成规定尺寸的较小卷（称为成品）。”

AIMMS 的这个pdf很好。

请注意，研究人员针对基本下料问题提出了相当多的变体。这些整数规划讲座很好地阐述了广义下料问题（参见第 17 页）

这些 MILP 问题并不很难表述，因为目标函数和约束遵循标准 CSP 的基本模式。对于有效解决这些问题的技术进行了大量的研究。

如果您可以使用 LP/IP 求解器，例如 CPLEX、R 或 Excel Solver（针对较小的问题），那么绝对值得制定您的问题并在这些求解器上进行尝试。

希望有帮助。