什么是将一维长度嵌套到预定义库存长度的有效算法？
例如，如果您需要以下数量和长度的钢筋：
5 x 2米
5 x 3米
5 x 4米
并且这些可以从10米长的钢筋中切割。如何计算切割10米长钢筋的图案，以使使用最少的钢筋条数？
此外，如何将多个库存长度纳入算法？
我有点时间来解决这个问题，所以我将写下我是如何解决的。希望对某些人有用。我不确定是否可以像这样回答自己的问题。如果更合适，管理员可以将其更改为答案。
首先感谢所有回答过我的人。这指引我找到了适当的算法; the cutting stock problem。
这篇文章也很有用; "Calculating a cutting list with the least amount of off cut waste"。
好的，进入解决方案。
我将在我的解决方案中使用以下术语;
我能利用这种冗余来减少计算组合的时间。我将重复的切割分组，并计算该组的独特组合。然后将这个组合列表附加到第二组中的每个独特组合中，以创建一个新组。
例如，对于切割 AABBC，过程如下。
这个例子产生了17种独特的组合，而不是31种（2^5-1）。几乎节省了一半的时间。
一旦所有的组合都被确定了，就是时候检查它们如何适应库存了。
第二步
这一步的目的是将第一步中确定的切割组合映射到可用的库存尺寸上。
这是一个相对简单的过程。对于每个切割组合，
例如，如果您需要以下数量和长度的钢筋：
5 x 2米
5 x 3米
5 x 4米
并且这些可以从10米长的钢筋中切割。如何计算切割10米长钢筋的图案，以使使用最少的钢筋条数？
此外，如何将多个库存长度纳入算法？
我有点时间来解决这个问题，所以我将写下我是如何解决的。希望对某些人有用。我不确定是否可以像这样回答自己的问题。如果更合适，管理员可以将其更改为答案。
首先感谢所有回答过我的人。这指引我找到了适当的算法; the cutting stock problem。
这篇文章也很有用; "Calculating a cutting list with the least amount of off cut waste"。
好的，进入解决方案。
我将在我的解决方案中使用以下术语;
- 库存: 一段将被切割成较小块的材料长度
- 切割: 从库存中切下的一段材料。可以从同一块库存中取多次切割。
- 废料: 在所有切割完成后留在库存中的材料长度。
- 确定所有可能的切割组合
- 确定每块材料可以采用哪些组合
- 找到最优的切割组合混合。
步骤1
使用N个切割，有2^N-1个唯一的切割组合。这些组合可以表示为二进制真值表。
其中A、B、C是独特的切割；
A B C | Combination
-------------------
0 0 0 | None
0 0 1 | C
0 1 0 | B
0 1 1 | BC
1 0 0 | A
1 0 1 | AC
1 1 0 | AB
1 1 1 | ABC
使用一些位运算符的for循环可以快速创建每个切割组合的分组。
对于较大的N值，这可能会非常耗时。
在我的情况下，存在多个相同的切割实例。这产生了重复的组合。
A B B | Combination
-------------------
0 0 0 | None
0 0 1 | B
0 1 0 | B (same as previous)
0 1 1 | BB
1 0 0 | A
1 0 1 | AB
1 1 0 | AB (same as previous)
1 1 1 | ABB
我能利用这种冗余来减少计算组合的时间。我将重复的切割分组，并计算该组的独特组合。然后将这个组合列表附加到第二组中的每个独特组合中，以创建一个新组。
例如，对于切割 AABBC，过程如下。
A A | Combination
-------------------
0 1 | A
1 1 | AA
将此组称为X。
将X附加到唯一的B实例中，
B B X | Combination
-------------------
0 0 1 | A
| AA
0 1 0 | B
0 1 1 | BA
| BAA
1 1 0 | BB
1 1 1 | BBA
| BBAA
把这个组称为Y。
将Y添加到C的唯一实例中，
C Y | Combination
-----------------
0 1 | A
| AA
| B
| BA
| BAA
| BB
| BBA
| BBAA
1 0 | C
1 1 | CA
| CAA
| CB
| CBA
| CBAA
| CBB
| CBBA
| CBBAA
这个例子产生了17种独特的组合，而不是31种（2^5-1）。几乎节省了一半的时间。
一旦所有的组合都被确定了，就是时候检查它们如何适应库存了。
第二步
这一步的目的是将第一步中确定的切割组合映射到可用的库存尺寸上。
这是一个相对简单的过程。对于每个切割组合，
calculate the sum of all cut lengths.
for each item of stock,
if the sum of cuts is less than stock length,
store stock, cut combination and waste in a data structure.
Add this structure to a list of some sort.
这将导致一个有效的嵌套切割组合列表。虽然不一定需要存储废料，因为可以通过切割长度和库存长度来计算，但是存储废料会减少第三步中所需的处理。
第三步
在此步骤中，我们将确定产生最小废料的切割组合。这基于步骤2生成的有效嵌套列表。
在理想情况下，我们将计算所有可能性并选择最佳解决方案。对于任何非平凡的切割集，计算所有可能性将需要很长时间。我们只能满足于非最优解决方案。有各种算法可用于完成此任务。
我选择了一种方法，该方法将寻找最少废料的嵌套。它将重复此操作，直到所有切割都已计算。
从三个列表开始
- cutList：所有所需切割（包括重复项）的列表。
- nestList：步骤2生成的嵌套列表。这是按最少废料到最多废料排序的。
- finalList：最初为空，这将存储将输出给用户的切割组合列表。
方法
pick nest from nestList with the least waste
if EVERY cut in the nest is contained in cutList
remove cuts from cutList
copy this nest into the finalList
if some cuts in nest not in cutList
remove this nest from nestList
repeat until cutlist is empty
通过这种方法，我成功地将一些典型测试数据的总浪费降低了约2-4%。希望有一天我能够重新审视这个问题，并尝试实现延迟列生成算法。这应该会得到更好的结果。
我希望这对其他遇到这个问题的人有所帮助。
大卫