如何编码最大集打包算法？

正如hivert所指出的，此问题是NP难题，因此没有有效的方法来做到这一点。但是，如果您的输入相对较小，您仍然可以将其拉出。毕竟，指数并不意味着没有可能。随着输入量的增加，指数问题很快变得不切实际。但是对于25套这样的东西，您可以轻松地对其进行暴力破解。

这是一种方法。假设您有 n 个子集，分别称为 S0 ， S1 ，…等。我们可以尝试子集的每种组合，然后选择基数最大的一个。只有2 ^ 25
= 33554432个选择，因此这可能足够合理。

一种简单的方法是注意到严格低于2 ^
N的任何非负数都代表子集的特定选择。查看数字的二进制表示形式，然后选择索引对应于打开的位的集合。因此，如果数字为11，则第0、1和3位为ON，这对应于组合[S0，S1，S3]。然后，您只需验证这三个集合实际上是不相交的。

您的过程如下：

1. 将i从0迭代到2 ^ N-1
2. 对于i的每个值，请使用打开的位找出相应的子集组合。
3. 如果这些子集成对相交，请使用此组合更新最佳答案（即，如果大于当前最佳答案，请使用此答案）。

或者，使用回溯来生成您的子集。这两种方法是等效的，以模块实现为代价。回溯将有一些堆栈开销，但是如果您在进行过程中检查不相交性，则会切断整个计算行。例如，如果S1和S2不是不相交的，则它将永远不会打扰包含它们的任何更大的组合，从而节省了时间。迭代方法无法以这种方式优化自身，但由于按位运算和紧密循环，因此是快速而有效的。

这里唯一不重要的问题是如何检查子集是否成对不相交。您还可以根据约束来选择各种技巧。

一种简单的方法是从一个空的set结构开始（从您选择的语言中选择任意内容），然后逐个添加每个子集中的元素。如果您命中了一个已经在集合中的元素，那么它会出现在至少两个子集中，并且您可以放弃这种组合。

如果原始集合 S 具有 m个 元素，并且 m 相对较小，则可以将每个元素映射到[0，m-1]范围，并对每个集合使用位掩码。因此，如果 m <=
64
，则可以使用Java
long来表示每个子集。打开与子集中元素相对应的所有位。由于按位运算的速度快，因此可以进行快速设置 *** 作。按位与对应于设置的交集，按位与是并集。您可以通过查看交集是否为空来检查两个子集是否不相交（即，对两个位掩码进行“与”运算得出0）。

如果元素很少，则仍然可以避免多次重复设置相交。您的集合很少，因此请预先计算哪些集合在开始时是不相交的。您可以只存储布尔矩阵D，使得D [i] [j] =
true，前提是i和j不相交。然后，您只需组合查找所有对即可验证成对的不相交性，而无需进行实际的集合 *** 作。