如何使用背包找到下料问题的最佳组合
How to find optimum combination for Cutting Stock Problem using Knapsack
编辑 (31-12-2019) - https://jonathan.overholt.org/projects/cutlist
以上是我正在寻找的免费项目的 link。我只是在寻找适当的指导，这样我才能让它发挥作用。
我正在努力最大限度地减少铝制滑动件的铝挤压切割浪费 Window 制造商，但我无法弄清楚我应该使用哪种 Algorithm/Data 结构来解决这个问题。
我做了基础研究，发现问题落在Cutting Stock Problem（也叫一维切割问题），Linear Programming Problem，Greedy Algorithm。但是我无法决定我应该选择哪一个以及如何开始。
问题简介：
基本上 window 制造商有 3 种尺寸 的 material 选项可供购买。
12 | 15 | 16 (IN FT)
现在输入的大小为 Window。
宽度 x 高度（英尺）
1) 6 x 8 - 10 Windows
2) 9 x 3 - 20 Windows
计算结果为（2 x 宽度）+（2 x 高度）。所以从上面的window尺寸来看，他们需要挤压如下。
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 或任何其他语言的数据结构和算法的问题。我的数学知识达不到标准，这就是为什么我在项目中实现逻辑时遇到问题并希望从社区获得一些帮助。
除了 brute-force 检查所有可能的组合之外，没有任何算法可以保证为您提供最佳解决方案。这显然不是一个好的算法，至少如果你有大数据集的话。
您应该看看 Simulated Annealing, MCTS 等启发式搜索算法。找到启发式搜索引擎的现有实现应该没有问题，这些引擎允许您为它们提供
- 一个输入集（material上的棋子随机分布），
- 一个转换函数（在material秒之间移动棋子），
- 和评价函数（浪费量）
并为您计算 near-optimal 解。
你考虑过单纯形算法吗？
您有一个最小化问题，可以将其转化为最大化问题，然后由算法解决，或者由对偶单纯形算法解决。
您会在 Google.
上找到实现
我会回应其他答案的观点：虽然这个问题可能有 "most correct" 解决方案，但您真正需要的是 "correct enough" 解决方案。
也就是说，我写了这个小附录来帮助理解您引用的项目中的代码：cutlist generator design notes
释义：
Each iteration starts by creating a new instance of the longest stock and placing as many pieces into it as will fit. The stock is then reduced to the smallest stock that all of the selected pieces still fit into. This is all repeated until no pieces remain.
另一个建议：确保清楚地识别您在算法中构建的所有假设。我假设更长的库存每单位更便宜并且它总是首选，但我被要求进行变化以优化最少数量的切割（捆绑切割）或跟踪并更喜欢首先使用以前运行的边角料。
一如既往：在设定假设之前非常清楚地了解客户的流程。
编辑 (31-12-2019) - https://jonathan.overholt.org/projects/cutlist
以上是我正在寻找的免费项目的 link。我只是在寻找适当的指导，这样我才能让它发挥作用。
我正在努力最大限度地减少铝制滑动件的铝挤压切割浪费 Window 制造商，但我无法弄清楚我应该使用哪种 Algorithm/Data 结构来解决这个问题。
我做了基础研究，发现问题落在Cutting Stock Problem（也叫一维切割问题），Linear Programming Problem，Greedy Algorithm。但是我无法决定我应该选择哪一个以及如何开始。
问题简介：
基本上 window 制造商有 3 种尺寸 的 material 选项可供购买。
12 | 15 | 16 (IN FT)
现在输入的大小为 Window。
宽度 x 高度（英尺）
1) 6 x 8 - 10 Windows
2) 9 x 3 - 20 Windows
计算结果为（2 x 宽度）+（2 x 高度）。所以从上面的window尺寸来看，他们需要挤压如下。
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 或任何其他语言的数据结构和算法的问题。我的数学知识达不到标准，这就是为什么我在项目中实现逻辑时遇到问题并希望从社区获得一些帮助。
除了 brute-force 检查所有可能的组合之外，没有任何算法可以保证为您提供最佳解决方案。这显然不是一个好的算法，至少如果你有大数据集的话。
您应该看看 Simulated Annealing, MCTS 等启发式搜索算法。找到启发式搜索引擎的现有实现应该没有问题，这些引擎允许您为它们提供
- 一个输入集（material上的棋子随机分布），
- 一个转换函数（在material秒之间移动棋子），
- 和评价函数（浪费量）
并为您计算 near-optimal 解。
你考虑过单纯形算法吗？ 您有一个最小化问题，可以将其转化为最大化问题，然后由算法解决，或者由对偶单纯形算法解决。 您会在 Google.
上找到实现我会回应其他答案的观点：虽然这个问题可能有 "most correct" 解决方案，但您真正需要的是 "correct enough" 解决方案。
也就是说，我写了这个小附录来帮助理解您引用的项目中的代码：cutlist generator design notes
释义：
Each iteration starts by creating a new instance of the longest stock and placing as many pieces into it as will fit. The stock is then reduced to the smallest stock that all of the selected pieces still fit into. This is all repeated until no pieces remain.
另一个建议：确保清楚地识别您在算法中构建的所有假设。我假设更长的库存每单位更便宜并且它总是首选，但我被要求进行变化以优化最少数量的切割（捆绑切割）或跟踪并更喜欢首先使用以前运行的边角料。
一如既往：在设定假设之前非常清楚地了解客户的流程。