算法:将 n 个给定集合的元素合并为 2 个空集合 A 和 B，使得 |A∩B|最少

Question

例子:给定一些集合 S1、S2、S3、S4、S5 和 2 个空集合 A 和 B。

• S1 = [1,2,3,4,5]

• S2 = [2,6]

• S3 = [7]

• S4 = [5]

• S5 = [1,2,3,4,5]

案例一)

• A = S1∪S3∪S4 = [1,2,3,4,5,7]

• B = S2∪S5 = [1,2,3,4,5,6]

• |A∩B| = 5

案例2)

• A = S1∪S5 = [1,2,3,4,5]

• B = S2∪S3∪S4 = [2,5,6,7]

• |A∩B| = 2

在这里，案例 2 是最少没有的场景。 A 和 B 之间的共同元素。

除了遍历所有组合的朴素方法之外，是否有一种算法方法可以找到 A 和 B 之间具有最少公共(public)元素的组合？

Answer 1

是否允许将所有内容放入集合 A？这样，您将得到 |A∩B| = 空集。

在你的例子中，不是合并:

• A = S1∩S2∩S4∩S5 = [1,2,3,4,5,6]

• B = S3 = [7]

导致更小的 |A∩B|这又是空集？