在定义的数字集中找到低于限制的最佳匹配范围

计算科学 迭代法 搜索
2021-11-28 01:38:02

我正在尝试计算一些木材切割的最佳切割组,以减少浪费。

所以:给定一组数字,目标是找到低于限制(木梁尺寸)的最佳匹配。

一组数字的例子:

const input = [
  4, 13.5, 17.5, 18.5, 20, 26, 43.5, 44.5, 
  45, 46, 54, 54.5, 55, 60, 61, 62, 70.5, 
  80.5, 103.5, 148.5, 78, 102, 10,
]

在我的情况下,限制是const limit = 300.

到目前为止我得到的结果示例:

SUM PARTS
300     148.5   80.5    61      10              
300     103.5   102     70.5    20      4           
300     78  62  60      55      45          
299.5   54.5    54      46      44.5    43.5    26  17.5    13.5
18.5    18.5

这个结果集是一组过于复杂和长时间运行的函数的输出,这些函数构建了一组所有可能的组合,然后搜索最佳组合。

问题是如何在不过度使用 CPU 周期的情况下解决这个问题?

1个回答

欢迎来到 SciComp!

您对子长度列表的大小有任何限制吗?您是在寻找“最佳”解决方案,还是“足够好”的解决方案?可以这么说,如果我们谈论启发式或硬数学,这个问题的答案会有所不同。

我会尝试通过提高丢弃效率来避免测试所有组合。循环遍历排序数组时,一旦达到超出限制的元素(普朗克的剩余长度),您可能会立即返回,并且所有后续元素无论如何都会更大。这样,您应该能够避免大部分计算工作。

您是否检查过现有算法的文献?也许你可以看看众所周知的Bin 打包问题并寻找现有的方法。