我正在寻找一种算法,能够处理以下描述的问题。我已经编写了一个算法(我认为它太专业化了,不能公开),尽可能地优化了它,但在更大的数字集上,它仍然太慢(随着成本的呈指数级增长)。解决方案在一台不错的计算机上应该不超过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 中的所有点。每个数字只能使用一次。
在我们的示例中,可能的解决方案是(虽然我不知道它是否是最佳的):
Y = (500, 100, 50; 1000, 200, 200; 2000, 1000, 500; 5000; 2000, 2000)
正如您可以看到的,两个标准“最少”和“接近”需要一些权衡。这就是为什么我的当前算法使用评分来找到“最佳”解决方案的原因。
以下是它目前的工作方式:
1.排序 M、排序 P,升序 2.删除数字太小以至于不能显著改变得分或者数字太大的数据 3.递归: 4.将 P 中的下一个点作为当前“目标”,加上或减去例如10% 5.添加来自 M 的下一个数字,并将其从 M 中删除 6.当靠近目标点时,转到步骤4。如果在结束点,则计算当前分配的得分并可能记忆它 7.否则,转到步骤5 8.从尝试数字返回时,取下一个更高的数字
它从不尝试两个相同的数字,只尝试升序,例如:
你会得到一组数字,例如:
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 中的所有点。每个数字只能使用一次。
在我们的示例中,可能的解决方案是(虽然我不知道它是否是最佳的):
Y = (500, 100, 50; 1000, 200, 200; 2000, 1000, 500; 5000; 2000, 2000)
正如您可以看到的,两个标准“最少”和“接近”需要一些权衡。这就是为什么我的当前算法使用评分来找到“最佳”解决方案的原因。
以下是它目前的工作方式:
1.排序 M、排序 P,升序 2.删除数字太小以至于不能显著改变得分或者数字太大的数据 3.递归: 4.将 P 中的下一个点作为当前“目标”,加上或减去例如10% 5.添加来自 M 的下一个数字,并将其从 M 中删除 6.当靠近目标点时,转到步骤4。如果在结束点,则计算当前分配的得分并可能记忆它 7.否则,转到步骤5 8.从尝试数字返回时,取下一个更高的数字
它从不尝试两个相同的数字,只尝试升序,例如:
- 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个,并且去掉许多较小的数字,该算法将非常快并找到一个好的解决方案。但是,如果我添加更多数字,特别是包括较小的数字,则运行时间从100ms上升到无限大。
你能给我一些提示如何解决这个问题吗?文献中是否有类似的算法可以处理该问题或其中的一部分?