如何利用背包找到切割库存问题的最佳组合

Question

编辑（31-12-2019）－https://jonathan.overholt.org/projects/cutlist

以上是免费项目的链接，这正是我正在寻找的。我只是在寻找适当的指导，以便我能让它发挥作用。

我正在努力最大限度地减少铝推拉窗制造商的铝挤压切割浪费，我不能找出我应该使用哪种算法/数据结构来解决这个问题。

我做了基础研究，发现问题属于下料问题（又称一维下料问题）、线性规划问题、贪婪算法。但我无法决定应该选择哪一个，以及如何开始。

问题简介：

窗户制造商基本上有3种尺寸的材料可供选择。

12 | 15 | 16 (IN FT)

现在输入的是窗口的大小。

宽度x高度（单位：英尺）

1） 6 x 8-10扇窗户

2） 9 x 3-20扇窗户

计算结果为（2 x宽度）（2 x高度）。因此，从上述尺寸的窗口，他们需要挤出如下。

1） 6英寸（英尺）大小的零件-

2）8'（FT）尺寸件-

3） 9英寸（英尺）大小的零件-

4）3'（FT）尺寸件-

使用背包，我们可以找出组合，但它有限制的尺寸只有1，而在我的情况下，我有3种不同的尺寸可供选择，我想为切割库存问题生成最佳组合。

我需要帮助，我应该如何处理上面的问题，关于Java或任何其他语言的数据结构和算法。我的数学知识没有达到标准，这就是为什么我在项目中实施逻辑时面临问题，并希望从社区获得一些帮助。

Answer 1

你考虑过单纯形算法吗？你有一个极小化问题，可以转化为极小化问题，然后用算法求解，或者用对偶单纯形算法求解。你可以在谷歌上找到实现。

Answer 2

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

也就是说，我写了这个小附录来帮助理解你提到的项目中的代码：cutlist generator design notes

意译：

每次迭代都从创建最长库存的新实例开始，并将尽可能多的零件放入其中。然后将库存减少到所有选定零件仍然适合的最小库存。这一切都会重复，直到没有碎片残留。

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

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

Answer 3

除了强力检查所有可能的组合外，没有任何算法能保证您获得最佳解决方案。这显然不是一个好的算法，至少在有大数据集的情况下不是。

您应该看看启发式搜索算法，如模拟退火、MCTS等。找到启发式搜索引擎的现有实现应该不成问题，这些实现允许您为它们提供

• 输入集（材料上的随机分布），

为你计算一个近乎最优的解。