给定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听到的问题吗？我希望能有一些细节，如果有一个有效的解决方案。

[注意]输入集的数量最多为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的一部分。