algorithm - 最大不相交集的集合

Question

给定一组 3 个数字，找到最大的不相交集。例如，令 C = {(3,4,5), (4,5,6), (1,2,3), (6,9,10), (7,8,9)}。此输入应返回 3，因为最大不相交集为 {(1,2,3), (4,5,6), (7,8,9)}。我如何编写一个程序来输出最大不相交集的集合？

我考虑过从选择所有 5 组开始。然后，查看每个集合，看看删除该元素是否会影响其余集合。如果我们拿走 (3,4,5)，它将允许我们保留 (4,5,6) 和 (1,2,3)。因此，它的净 yield 是+1。我们应该将其从最终列表中删除。然后，如果我们拿走 (4,5,6)，它会让我们保留 (6,9,10)。净 yield 为0，所以不要去掉。删除 (1,2,3) 不会有任何影响。不要删除它。删除 (6,9,10) 将允许我们保留 (7,8,9)。不确定这是否有意义，但请告诉我您的想法!

Answer 1

如果这三个数字总是连续的，那么这有一个简单的动态规划解决方案(使用递归公式计算可以使用数字 1..i 放置的最大集合)。

但是，如果这个约束不总是正确的，那么这个问题就是 NP 难的。它是 NP 难是因为它可以用来解决 NP-complete 3-dimensional matching problem .

例如，假设我们正在匹配 X、Y、Z 中的元素。我们可以使用数字 1..|X| 为每个允许的匹配构造集合在第一个位置，|X|+1..|X|+|Y|在第二个位置和|X|+|Y|..|X|+|Y|+|Z|在第三的位置。一旦我们构建了这些集合，我们就可以使用算法来解决 3 维匹配问题。