c++ - 查找最大对数的有效算法

标签 c++ algorithm

<分区>

从数字对列表中找到数字对以形成最大数量的数字对的最快方法是什么?

例如:我有 6 个数字:0、1、2、3、4、5

以下是有效的对:

0 1
0 2
0 3
1 4
3 5

现在,一旦一个数字包含在一对中,该数字就不能包含在另一对中。

也就是说,如果我选择了 0 1 对,我不能再次选择 0 2,因为我已经使用过一次 0。

我需要从有效对列表中选择对,以便获得最大对数。

根据示例:

如果我选择以下对:

0 1
3 5

请注意,我将只能选择这两对,这样就不会重复任何数字,并且会留下 2 和 4。

但如果我选择以下对:

0 2
1 4
3 5

我得到了三对,没有一个数字是单独留下的。类似地,从给定的列表中,我需要计算我可以制作的最大对数。最有效的方法是什么?

最佳答案

可以使用 Bloossom 算法以多项式时间复杂度解决此问题: http://en.wikipedia.org/wiki/Blossom_algorithm

形成一个图,其中每个数字是节点,并将每对连接到边缘。在此图上运行上述算法以找到解决方案。

关于c++ - 查找最大对数的有效算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29564756/

相关文章:

java - 从python到java的并行赋值变量(Pi算法)

algorithm - 如何将递归函数模型模拟为具有堆栈的迭代函数模型?

python - 对平面内容执行文本处理以包括自定义标记的处理

c++ - 错误 : type/value mismatch at argument 1 in template parameter list for 'template<class T> class QList'

c++ - 关于 rect ROI 的 OpenCv 断言失败

c++ - 处理孙子控件的 WM_NOTIFY

javascript - 使用两个指针的算法的时间复杂度。是0(n)还是0(n^2)

C++ 数组初学者

c++ - boost 条件变量

javascript - 偏置随机 boolean 值的优雅方式