给定数字和间隔集的分布算法

Question

我正在寻找一种算法,它可以解决下面描述的问题.我已经编写了一个算法(我认为它过于专业化,无法发布),尽可能地优化,但在更大的数字集上它仍然太慢(因为成本呈指数增长).在合适的计算机上,解决方案应该不超过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)

正如您所看到的那样,这两个标准的最小和最接近的某种权衡.这就是为什么我当前的算法使用评分来找到"最佳"解决方案.

以下是它目前的工作原理:

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增加到无穷大.

你能给我一个提示,如何处理这个问题？文献中是否有类似的算法可以处理问题或其中的一部分？

Answer 1

类似于硬币找零问题：http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Greedy/greedyIntro.htm

唯一的区别是你的“硬币”供应有限（可以通过将数组中的项目标记为“已使用”来轻松解决）并且你不需要达到确切的数量 - 正负 10% 是对你有好处（这样你就可以丢弃 M 中小于目标值 10% 的元素）