我正在做一个生产铝型材切割清单的项目。

铝型材的长度为5m。

我列出了一些需要从5m铝型材中切出的较小长度的清单。

需要按较小的长度切割，以便从5m长度的铝型材中产生最少的切屑。

目前，我以这样的方式订购切割清单：通常，较小长度的最长的一个首先被切割，较小长度的最短的最后一个被切割。该规则的例外情况是，只要较短的长度不适合5m铝型材剩余长度，我将使用适合的最长的较短长度。

这似乎产生了一个非常有效的(几乎没有切屑的浪费)切割清单，并且计算时间不长。但是我想，即使切割清单非常有效，也不一定是最有效的。

有谁知道一种可以在合理的时间内计算出最有效的切割清单的方法？

编辑：感谢回答，我将继续使用"贪婪"方法，因为它似乎做得很好(完成任何人为尝试创建有效切割清单的尝试)并且速度非常快。

解决方案

回答

这是一个有趣的问题，因为我想这取决于我们要生产的每种长度的数量。如果它们都是相同的数量，并且我们可以将每个不同的长度放在一个5m的挤塑件上，那么我们将获得最佳的解决方案。

但是，如果它们不都适合一个挤出，那么我们会遇到更大的问题。要为每个长度保留相同数量的切口，我们需要计算一个挤出可适合多少个长度(不一定按顺序排列)，然后按顺序遍历每个挤出。

回答

这是一个有效解决的经典难题。我们描述的算法听起来像是贪婪算法。请参阅此Wikipedia文章以获取更多信息：切削库存问题

回答

恐怕没有关于此问题的具体想法，但是我们可以研究一种"遗传算法"(它将采用类似的方法)...

将长度切割成随机顺序，并根据与理想解决方案的匹配程度(零浪费，大概是0％)为该顺序打分。

然后，反复对该顺序进行随机更改，然后重新评分。如果分数更高，则放弃结果。如果分数较低，请保留该分数并将其用作下一次计算的基础。继续努力，直到分数在可接受的范围内。

回答

实际上，由于材料的大小是固定的，但是要求不是固定的，所以这是垃圾箱包装的问题。

再次，维基百科来营救！

(有些事情我可能也要去找工作，是的！)

回答

正如Wheelie所提到的，我们所描述的确实确实是切削问题，而不是装箱问题，因为我们试图将浪费(残余物的总和)降到最低，而不是使用挤出的次数。

这两个问题都很难解决，但是我们提到的"最佳拟合"算法(使用适合当前拉伸的最长"较小长度")可能会以非常低的复杂度为我们提供很好的答案。

回答

我也在这个问题上苦苦挣扎(我的问题的长度是6 m)。

我正在研究的解决方案有点丑陋，但我不满意解决方案。让我解释：

库存尺寸5 m

需要缩小尺寸(每个尺寸1个)：

** 3,5

1个

1,5 **

解决方案：

3,5 | 1，浪费0.5

1,5，剩余3,5

看到问题了吗？

我正在研究的解决方案->蛮力

1测试所有可能的解决方案

2根据他们的浪费订购解决方案

3选择最佳解决方案

4从" Universe"中删除解决方案中的项目

5转到1

我知道这很耗时(但是我要吃1h30 m午餐...所以... :))

我确实需要最佳解决方案(我在excel中手工(+-)做一个完美的最佳解决方案)不仅是因为我很着迷，而且产品也不便宜。

如果有人有更好的简单解决方案，我会喜欢的