假设我们有一个有限集 S 和一个 S 的子集列表。然后，集合打包问题询问列表中的一些 k 子集是否成对不相交。该问题的优化版本，最大集打包，要求列表中成对不相交集的最大数量。
http://en.wikipedia.org/wiki/Set_packing
所以让S = {1,2,3,4,5,6,7,8,9,10}
and `Sa = {1,2,3,4}`
and `Sb = {4,5,6}`
and `Sc = {5,6,7,8}`
and `Sd = {9,10}`
则成对不相交集的最大数量为 3 ( Sa, Sc, Sd )
我找不到任何有关所涉及算法的文章。你能解释一下吗？
我的做法：
根据大小对集合进行排序。从最小尺寸的集合开始。如果下一个集合中没有元素与当前集合相交，那么我们将集合合并并增加最大集合的计数。这听起来不错吗？有更好的想法吗？
正如 hivert 指出的那样，这个问题是 NP 难的，所以没有有效的方法来做到这一点。但是，如果您的输入相对较小，您仍然可以将其关闭。毕竟，指数并不意味着不可能。只是随着输入大小的增长，指数问题很快变得不切实际。但是对于像 25 套这样的东西，你可以很容易地暴力破解它。
这是一种方法。假设您有n个子集，称为S0、S1、...等。我们可以尝试子集的每种组合，并选择具有最大基数的那个。只有 2^25 = 33554432 个选择，所以这可能足够合理。
一个简单的方法是注意任何严格低于 2^N 的非负数表示子集的特定选择。查看数字的二进制表示，并选择其索引对应于打开的位的集合。因此，如果数字为 11，则第 0、第 1 和第 3 位为 on，这对应于组合 [S0, S1, S3]。然后您只需验证这三个集合实际上是不相交的。
您的程序如下：
或者，使用回溯来生成您的子集。这两种方法是等效的，模实现权衡。回溯会产生一些堆栈开销，但如果您在进行过程中检查不相交性，则可能会切断整条计算线。例如，如果 S1 和 S2 不是不相交的，那么它将永远不会打扰包含这两个的任何更大的组合，从而节省一些时间。迭代方法不能以这种方式优化自身，但由于按位运算和紧密循环，因此快速高效。
这里唯一重要的是如何检查子集是否成对不相交。您也可以在这里使用各种技巧，具体取决于约束条件。
一种简单的方法是从一个空集结构开始（从您选择的语言中选择您想要的任何内容）并从每个子集中逐个添加元素。如果你碰到了一个已经在集合中的元素，那么它至少出现在两个子集中，你可以放弃这个组合。
如果原始集合S有m个元素，并且m相对较小，您可以将它们中的每一个映射到范围 [0, m-1] 并为每个集合使用位掩码。因此，如果m <= 64，您可以使用 Java long 来表示每个子集。打开与子集中元素对应的所有位。由于按位运算的速度，这允许极快的设置操作。按位与对应集合交集，按位或是并集。您可以通过查看交集是否为空来检查两个子集是否不相交（即，对两个位掩码进行“与”运算会得到 0）。
如果你没有这么少的元素，你仍然可以避免多次重复设置的交叉点。你的集合很少，所以在开始时预先计算哪些是不相交的。您可以只存储一个布尔矩阵 D，使得 D[i][j] = true 如果 i 和 j 不相交。然后您只需查找组合中的所有对以验证成对的不相交性，而不是进行真正的集合操作。
您可以通过搜索最大独立集来解决集装箱问题。您将问题编码如下：
然后，如果没有两个具有两个相关顶点的顶点，您将不会有一个最大的顶点集。不幸的是，这是一个 NP-Hard 问题。任何已知的算法都是指数的。