algorithm - 给定n组整数，如何最大化非重叠集的数量

Question

给定n组整数，如何最大化非重叠集的数量？

例如，让给定的sets是，

{1,2,3}
{1,4,5}
{6,7,8}
{2,3}
{8,9}
{9}

那么答案将是4，

 {1,4,5}, {6,7,8}, {2,3}, {9}

{1,2,3}并且{1,4,5}不能由不重叠的集合组成，因为 1 在两个集合中都很常见。这是一个NP听说的问题吗？如果有针对该问题的有效解决方案，我将期待一些细节。

[NB]输入集的数量最多为1000 个，每个集最多包含1000 个整数。

Answer 1

这是一个最大独立集问题，其中您的集合对应于节点，并且与共享至少一个元素的集合对应的节点之间有一条边。它是 NP-Hard，也很难近似为一个常数因子。

您仍然可以尝试解决它，例如使用整数线性规划：

maximize: sum x[i]

for each pair of sets (i,j) that overlap: x[i] + x[j] <= 1

x[i]是一个布尔值，指示第 i 个集合是否是您正在查找的 MIS 的一部分。

Answer 2

在这种情况下，答案很简单：假设没有集合是空的，您总是可以找到一个最大集合，其中没有集合是原始集合之一的超集 - 因为非空集合及其超集或重叠并且不能两者都在最大集，并且超集可以用子集替换而不会产生任何重叠。

在这里，可以排除 {1, 2, 3} 和 {8, 9}，很高兴剩下的四个集合不重叠。