我正在寻找一种算法,它可以处理下面描述的问题。我已经写了一个算法(我认为它太专业了,无法发布),尽可能地优化,但在更大的数字集上它仍然太慢(因为成本呈指数增长)。在一台像样的计算机上,该解决方案应该不超过 5 秒。
你得到一组数字,例如:
M = { 1, 1, 1, 2, 2, 2, 5, 5, 5, 10, 10, 10, 10, 20, 50, 50, 50, ... , 10000, 10000, 20000, 20000 }
不必有特殊的结构(虽然他们在这里)。
你会得到一组“目标点”,还有数字,例如:
P = { 670, 2010, 5600, 10510, 15000}
目标是从 M 中取出最少数量的数字,其中,当您按确定的顺序添加它们时,您会得到尽可能接近P 中所有点的中间结果。您只能使用 M 中的每个数字一次。
在我们的示例中,一个可能的解决方案是(尽管我不知道它是否是最好的):
Y = ( 500, 100, 50 ; 1000, 200, 200; 2000, 1000, 500; 5000; 2000, 2000)
正如您所看到的,这两个标准最少且接近某种权衡。这就是为什么我当前的算法使用评分来找到“最佳”解决方案。
以下是它目前的工作方式:
- 排序 M,排序 P,升序
- 删除太小而无法相关更改分数或太大的数字
- 递归:
- 将 P 中的下一个点作为当前“目标”,加上负值,例如 10%
- 从 M 中添加下一个数字,如果 M 则将其删除
- 接近目标点时,转到4。如果在终点,计算当前分布的分数并可能记住它
- 否则转到 5
- 从尝试号码回来时,取下一个更高的号码
它从不尝试两个相同的数字,只尝试升序,例如:
- 100, 100, 100, 50, 50, 20, 10
- 100, 100, 100, 50, 50, 20, 20
- 100, 100, 100, 50, 50, 50, 10
- 100, 100, 100, 50, 50, 50, 20
- 100, 100, 100, 50, 50, 50, 50
- 100, 100, 100, 100
- 100, 100, 100, 100, 10
- 100, 100, 100, 100, 20
- ...
每个数字大约有 5 个,并删除许多较小的数字,该算法非常快并且找到了一个很好的解决方案。但是当我添加更多数字或特别是包含更小的数字时,运行时间从 100 毫秒上升到无穷大。
你能给我一个提示,如何处理这个问题?文献中是否有任何类似的算法可以处理该问题或其中的一部分?