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

Question

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

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

我正在努力减少铝滑动窗制造商的铝挤压切割的浪费，但我无法弄清楚我应该使用哪种算法/数据结构来解决这个问题。

我做了基础研究，发现问题属于切削库存问题（也称为一维切削问题），线性规划问题，贪心算法。但我无法决定我应该选择哪一个以及如何开始。

问题简介：

基本上，窗户制造商有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 或任何其他语言中的数据结构和算法，我应该如何处理上述问题需要帮助。我的数学知识达不到标准，这就是为什么我在项目中实现逻辑时遇到问题并希望从社区获得一些帮助。

标签： javaalgorithmmathlinear-programming

Answer 1

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

你应该看看启发式搜索算法，如模拟退火、MCTS等。找到启发式搜索引擎的现有实现应该没有问题，允许您向他们提供

• 输入集（材料上碎片的随机分布），
• 过渡功能（在材料之间移动碎片），
• 和一个评估函数（废物量）

并为您计算一个接近最优的解决方案。