3

这是我在 stackoverflow 上的第一篇文章。

我需要为金融应用程序提供算法建议。假设我们有 2 个这样的数字列表（是的，它们是银行交易）：

List 1          | List 2
-------------------------------------
1000            | 200
7000            | 300
3000            | 10000
16000           | 500
                | 16000
                | 4100

考虑到一些条件，我需要将数字相互匹配：

  1. 匹配可以是一对一的、一对多的，甚至是多对多的。所以，这里两个 16000 匹配（一对一），列表 1 中的 1000 匹配列表 2 中的 200+300+500（一对三），列表 2 中的 10000 匹配列表 1 中的 7000+3000（一- to-two)，依此类推。

  2. 一个人物可以在不止一场比赛中使用。

  3. 两个列表中的数字数量可能相等，也可能不相等。

  4. 一对多匹配中的最大图形数应该是可设置的。

  5. 多对多匹配不是必须的。但如果我们也有它们那就太好了！

  6. 有些数字可能无法匹配。没关系。

我正在做的是使用两个复杂的嵌套循环。它有效，但随着数字数量或每场比赛中允许的最大数字数量的增加，需要很长时间才能完成！

有没有更好的算法来做到这一点？

4

2 回答 2

3

我认为我的断言是正确的，如果我错了，那么我会踢你的计算的内核是 NP 难的，这意味着你（非常）不太可能找到多项式时间的解决方案. 您的内核是，给定一个数字（例如10000）和一个其他数字的列表，找到列表中总和为单个数字的所有子集。

这个核是子集和问题的一种变体。

鉴于此，您可以找到更好的算法是有限制的，并且您对找到“快速”算法的期望可能会令人失望。

为了使您的算法更快，我建议您首先对两个列表进行排序。从列表 1 中取出第一个数字，从列表 2 中取出小于或等于列表 1 中的数字的所有数字，找出匹配项，重复...然后按数字向下处理列表 2 ...

于 2013-02-14T13:33:13.753 回答
0

为此，您首先生成每个列表的组合。例如，对于列表 1，组合是：

1000
3000
7000
16000
1000
1000 1000 1000 1000 1000
1000 16000
3000 7000
3000 3000 16000
7000 16000
1000 1000 3000
1000 1000 1000 1000 16000
1000 1000 16000 16000
3000 7000 16000
1000 1000 1000 1000 7000 16000 16000

对于每个组合，您生成组合中项目的总和。现在你有两个总和列表。为了解决这个问题，你将两个列表相交。有多种算法可以执行交叉路口。一种简单的方法是将两个列表中较小的一个变成二叉树。然后，对于较大列表中的每个项目，您可以在二叉树中找到它。该算法具有 n*log(n) 时间复杂度。

于 2013-02-14T16:16:56.047 回答