如何使用背包找到切削问题的最佳组合

Question

我正在努力最大程度地减少用于铝推拉窗制造商的铝挤压切割的浪费，而且我无法弄清楚该问题应该使用哪种算法/数据结构。

我进行了基础研究，发现问题出在切削料问题（也称为一维切削问题），线性规划问题，贪婪算法。但是我无法决定应该选择哪一个，以及如何开始。

问题简介：

基本上，窗户制造商要购买3种尺寸的材料。

12 | 15 | 16 (IN FT)

现在输入将是Window的大小。

宽x高（英尺）

1）6 x 8-10窗口

2）9 x 3-20视窗

计算为（2 x宽度）+（2 x高度）。因此，从上述尺寸的窗口中，它们需要按以下方式进行挤压。

1）6'（FT）尺寸--2 x 10 = 20

2）8'（FT）尺寸--2 x 10 = 20

3）9'（FT）尺寸--2 x 20 = 40

4）3'（FT）尺寸--2 x 20 = 40

使用背包，我们可以找到组合，但它只能将尺寸限制为1，而在我的情况下，我有3种不同的尺寸可供选择，我想针对切削材料问题生成最佳的最佳组合。

在使用Java或任何其他语言编写有关数据结构和算法的上述问题时，我将需要帮助。我在数学方面的知识还不是很出色，这就是为什么我在实施项目逻辑时遇到问题，并且希望从社区中获得一些帮助。

Answer 1

除了蛮力检查所有可能的组合之外，没有算法可以保证为您提供最佳解决方案。显然，这不是一个好的算法，至少在您拥有大量数据集的情况下不是。

您应该看看启发式搜索算法，例如Simulated Annealing，MCTS等。找到启发式搜索引擎的现有实现，让您为他们提供

• 输入集（材料上的碎片的随机分布），
• 过渡功能（在材料之间移动零件），
• 和评估功能（浪费量）

并为您计算出接近最佳的解决方案。

Answer 2

我会回应其他答案的观点：虽然这个问题可能有一个“最正确”的解决方案，但您真正寻找的是一个“足够正确”的解决方案。

也就是说，我写了这个小附录来帮助理解您引用的项目中的代码：cutlist 生成器设计说明

释义：

每次迭代都首先创建最长库存的新实例，并将尽可能多的部件放入其中。然后，库存被减少到仍然适合所有选定部件的最小库存。这一切都会重复进行，直到没有碎片为止。

另一条建议是：确保清楚地识别您在算法中构建的所有假设。我的假设是，单位库存越长越便宜，而且总是首选，但有人要求我进行一些变化，以优化最少的切割次数（捆绑切割），或者跟踪并更喜欢首先使用以前运行的边角料。

一如既往：在设定假设之前，非常清楚地了解客户的流程。