5

我正在寻找一种算法，它可以处理下面描述的问题。我已经写了一个算法（我认为它太专业了，无法发布），尽可能地优化，但在更大的数字集上它仍然太慢（因为成本呈指数增长）。在一台像样的计算机上，该解决方案应该不超过 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 个，并删除许多较小的数字，该算法非常快并且找到了一个很好的解决方案。但是当我添加更多数字或特别是包含更小的数字时，运行时间从 100 毫秒上升到无穷大。

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

4

3 回答 3

0

这有点类似于背包问题。

于 2009-08-15T06:35:38.420 回答
0

让我试试，它可能不是最好的，但应该很好用。我在这里使用 PHP -

1) 对 M 中的值及其计数进行分类：我们称之为 C

$C = array_count_values( $M );

This gives us:
Array
(
    [1] => 3
    [2] => 3
     ...
    [20] => 1
     ...
)

2）从P中取出第一个数，对M进行二分查找，得到离P1最近的数N1（N1 < P1）。从 C 中减去相应的计数

    So say you get 500 which is nearest to 670. Now subtract $C[500] - 1.
You can validate if count is not 0 and if zero get the next lower number from M.

3) 获取 P1-N1 并再次对该数字进行二分搜索并返回一个最接近的值。将此添加到 N1 并继续循环，直到获得最接近的总和。

4) 对 P 的所有成员重复第 2 点和第 3 点。

二分搜索是这里的关键部分，应该足够高效。

于 2009-08-15T08:04:47.990 回答
0

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

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

于 2009-08-15T13:13:35.150 回答