算法问题：最佳匹配子集

我正在构建一个匹配交易的程序。以下是我目前面临的问题的解读。我需要一些关于算法的帮助。算法问题：最佳匹配子集

给定两组具有相似属性（交易日期，账户，符号）的交易A和B，我需要在A和B内找到交易a的子集，其中sum（a）最接近总和（b）。这里sum（）是该子集的特定属性（净钱）的总和。需要最接近的匹配的原因是，如果我们没有得到完美的匹配（理想情况），我们希望下一个最接近的匹配。注意：sum（a）可以大于或小于sum（b）。

我明显想要做到这一点，而不使用强制方法来生成A和B的所有组合并进行比较。

我觉得这可以用一些动态编程方法来完成，但我无法提出任何具体的东西。将不胜感激任何帮助。

来源

2011-03-21 user668661

符号的最知名的样品确实大快建设：来让a.netMoney只是'了'。因此，给定A = {a，e，i}和B = {b，c}，蛮力不仅仅是寻找（abs（a - b），abs（a - c） b），...abs（i-c）），但是（X-Y）的左边可以是A的单个元素的每个和，即：（（a + e）-b）...也是？ – 2011-03-21 02:11:23

是的。那就对了。 – user668661 2011-03-21 02:27:29

这个问题是NP-hard。

该证明是从子集和减少，这是已知是NP难。给定子集和的任何实例，其中我们被赋予一组S元素进行求和，并且给出一个目标数k，我们可以通过让A成为集合S并让B成为单一集合{k}来构造你的问题的一个实例。。如果我们解决你的问题，并发现最接近的匹配不完全是k，那么我们知道无法总结S的一个子集来获得k。否则，如果有一种方法可以将S的元素总和为k，那么匹配将完全等于k，并且我们知道某个子集确实加起来了目标。

因为这个问题是NP难的，所以你不应该期待一个能够在多项式时间运行的解决方案，或者它比蛮力更好。我想你需要稍微放松一下，以获得好的结果。

来源

2011-03-21 02:21:24 templatetypedef

它会帮助我建立一定的宽容度，并找到属于该范围内的所有子集而不是简单的最佳匹配？ – user668661 2011-03-21 02:30:51

这可能会有所帮助，但请记住，有多个指数级的子集可以查看，并且任何列出多个子集的算法如果产生太多的输出结果都会遇到麻烦。不知道更多关于这个问题的信息，我不知道我还能提供多少帮助......你能详细谈谈你想要做什么吗？ – templatetypedef 2011-03-21 02:32:15

哎哟，这听起来像是类固醇subset-sum。对于你的问题规模（A和B的元素数量）有一个想法是很好的。问题肯定会是NP难题，因此您可能无法使用如下所示的精确解决方案。

一个简单的DP解决方案是为每个可能的总和值分别求解A和B的子集和。因此，如果每个集合最多有10个元素可以在0到50之间，那么对于A和B，使用DP来回答0到500之间的X的问题“是否有一个子集与X和？”。然后只是看看他们有哪些共同点，或者找出A中某个可能总和到B中某个可能总和的最小距离。

（注意：我说'简单'，不是'高效'！但是由于NP硬度等原因，没有解决方案以大于O的速度大大快于此）

来源

2011-03-21 02:27:02 usul

因此，对于强力算法，我们构建A和B的超集，并构建所有的组合他们，总结他们，建立绝对的总和，并找到最低？

sa = superset (A) //() (a) (e) (i) (a, e), (a, i) (e, i) (a, e, i) 
sb = superset (B) 

sas = supersetAsums // 0, a, e, i, a+e, a+i, e+i, a+e+i 
sbs = supersetAsums 

ssas = sorted (sas) 
ssbs = sorted (sbs)

现在，你可以通过两个列表循环，如果SSAS（I）<办学团体（J）你增加Ĵ，否则增量我，看的ABS（DIFF）是否比当前分钟（ABS（差异较小））。

这里的问题是子集，它得到N. :)

来源

2011-03-21 02:27:50

算法问题：最佳匹配子集

回答

相关问题