algorithm - 给定一定数量的数字集，找到一组不包括任何给定数字的数字集

Question

给定一定数量的数字集合(例如 0-20)，我们被要求找到 0-20 中不包含任何给定集合的最大数字集合(它可以包含集合中的数字，但不是整套)例如:设置最大数 8 并给定集合

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

一个最大解是集合{1, 3, 5, 6, 8}。我正在考虑将其表示为图形，然后将其引入最大独立集问题，但这似乎只有当集合仅由成对组成时才有效，这是不成立的。有什么想法吗？提前致谢。

Answer 1

为每个集合使用一个位图，设置适当的位。如果少于 32 个成员，你可以只使用一个 uint32_t。然后可以通过使用特定位图屏蔽掉所有成员(即所有集合的并集)，然后对特定位图使用 xor 来计算全集包含。如果是子集，结果将全为 0，否则结果将是最大独立集的成员。