Select 最多不重叠的元素，使它们的大小之和最大化
Select the most elements that do not overlap so that the sum of their size is maximized
我正在尝试找到解决以下问题的算法。
假设我有多个对象 A、B、C...
我有这些对象的有效组合列表。每个组合的长度为 2 或 4。
例如。 AF、CE、CEGH、ADFG...等等。
对于两个对象的组合，例如。 AF，组合的长度为2。对于四个对象的组合，例如CEGH，组合的长度。
我只能选择不重叠的组合，即我不能选择 AF 和 ADFG，因为它们都需要对象 'A' 和 'F'。我可以选择 AF 和 CEGH 的组合，因为它们不需要共同的对象。
如果我的解只有AF和CEGH这两个组合，那么我的objective就是组合的长度之和，就是2+4=6。
给定一个对象列表及其有效组合，我如何选择彼此不重叠的最有效组合，以便最大化组合长度的总和？我不想将它表述为 IP，因为我正在处理一个包含 180 个对象和 1000 万个有效组合的问题实例，并且使用 CPLEX 解决 IP 的速度非常慢。寻找其他一些优雅的方法来解决它。我可以将其转换为网络吗？并使用最大流算法解决它？还是动态程序？对如何解决这个问题感到困惑。
您可以将此问题减少到 maximum weighted clique problem，不幸的是，NP-hard。
构建一个图，使每个组合都是一个顶点，权重等于组合的长度，如果对应的组合不共享任何对象（即，如果您可以同时选择它们），则连接顶点.然后，当且仅当它是该图中的一个集团时，该解决方案才有效。
在google上简单搜索一下，提出了很多这个问题的近似算法，比如this one。
我第一次尝试将此问题显示为 NP-hard 是错误的，因为它没有考虑到仅允许大小 2 或 4 的组合这一事实。但是，使用 to reduce from (3DM)，我们可以证明问题仍然是 NP-hard.
我将证明您的问题 ("Given a set O of objects, and a set C of combinations of either 2 or 4 objects from O, and an integer m, does there exist a subset D of C such that all sets in D are pairwise disjoint, and the union of all sets in D has size at least m?") 的自然决策问题形式是 NP-hard。显然，优化问题（即您的原始问题，我们在其中寻找最大化上述 m 的组合的实际子集）至少与这个问题一样难。 （要看出优化问题并不比决策问题 "much" 难，请注意，您可以首先使用对 m 的二分搜索找到存在解决方案的最大 m 值，其中您在每个位置解决决策问题步骤，然后，一旦找到这个最大的m值，解决一系列决策问题，其中每个组合依次被删除：如果删除某个特定组合后的解决方案仍然是"YES"，那么它也可能是排除所有未来的问题实例，而如果解决方案变为 "NO"，则有必要在解决方案中保留此组合。）
给定 3DM 的实例 (X, Y, Z, T, k)，其中 X、Y 和 Z 是彼此成对不相交的集合，T 是 X*Y*Z 的子集（即，一组有序的三元组，分别具有来自 X、Y 和 Z 的第一、第二和第三分量）并且 k 是一个整数，我们的任务是确定是否存在 T 的任何子集 U 使得 |U| >= k 并且 U 中的所有三元组都是成对不相交的（即，回答问题，"Are there at least k non-overlapping triples in T?"）。要将 3DM 的任何此类实例变成您的问题的实例，我们需要做的就是通过为每个三元组添加不同的虚拟值，从 T 中的每个三元组创建一个新的 4 组合。问题的构造实例中的对象集将由 X、Y、Z 和 |T| 的并集组成我们创建的虚拟值。最后，将m设置为k。
假设原始3DM实例的答案是"YES"，即T中至少有k个non-overlapping个三元组，那么这个解中的k个三元组中的每一个都对应一个输入 C 中的 4 组合到您的问题，并且这些 4 组合中没有两个重叠，因为通过构造，它们的第 4 个元素都是不同的，并且假设。因此，在您的问题实例中至少有 m = k non-overlapping 4 种组合，因此该问题的解决方案也必须是 "YES".
在另一个方向上，假设您的问题的构造实例的解决方案是 "YES"，即 C 中至少有 m non-overlapping 个 4-组合。我们可以简单地取每个 4 组合的前 3 个元素（丢弃第四个）产生一组 k = m non-overlapping T 中的三元组，因此原始 3DM 实例的答案也必须是 "YES" .
我们已经证明，一个问题的 YES-answer 意味着另一个问题的 YES-answer，因此一个问题的 NO-answer 意味着另一个问题的 NO-answer。因此问题是等价的。您的问题实例显然可以在多项式时间和 space 中构造。由此可见，您的问题是 NP-hard.
我正在尝试找到解决以下问题的算法。
假设我有多个对象 A、B、C...
我有这些对象的有效组合列表。每个组合的长度为 2 或 4。
例如。 AF、CE、CEGH、ADFG...等等。
对于两个对象的组合，例如。 AF，组合的长度为2。对于四个对象的组合，例如CEGH，组合的长度。
我只能选择不重叠的组合，即我不能选择 AF 和 ADFG，因为它们都需要对象 'A' 和 'F'。我可以选择 AF 和 CEGH 的组合，因为它们不需要共同的对象。 如果我的解只有AF和CEGH这两个组合，那么我的objective就是组合的长度之和，就是2+4=6。
给定一个对象列表及其有效组合，我如何选择彼此不重叠的最有效组合，以便最大化组合长度的总和？我不想将它表述为 IP，因为我正在处理一个包含 180 个对象和 1000 万个有效组合的问题实例，并且使用 CPLEX 解决 IP 的速度非常慢。寻找其他一些优雅的方法来解决它。我可以将其转换为网络吗？并使用最大流算法解决它？还是动态程序？对如何解决这个问题感到困惑。
您可以将此问题减少到 maximum weighted clique problem，不幸的是，NP-hard。
构建一个图，使每个组合都是一个顶点，权重等于组合的长度，如果对应的组合不共享任何对象（即，如果您可以同时选择它们），则连接顶点.然后，当且仅当它是该图中的一个集团时，该解决方案才有效。
在google上简单搜索一下，提出了很多这个问题的近似算法，比如this one。
我第一次尝试将此问题显示为 NP-hard 是错误的，因为它没有考虑到仅允许大小 2 或 4 的组合这一事实。但是，使用
我将证明您的问题 ("Given a set O of objects, and a set C of combinations of either 2 or 4 objects from O, and an integer m, does there exist a subset D of C such that all sets in D are pairwise disjoint, and the union of all sets in D has size at least m?") 的自然决策问题形式是 NP-hard。显然，优化问题（即您的原始问题，我们在其中寻找最大化上述 m 的组合的实际子集）至少与这个问题一样难。 （要看出优化问题并不比决策问题 "much" 难，请注意，您可以首先使用对 m 的二分搜索找到存在解决方案的最大 m 值，其中您在每个位置解决决策问题步骤，然后，一旦找到这个最大的m值，解决一系列决策问题，其中每个组合依次被删除：如果删除某个特定组合后的解决方案仍然是"YES"，那么它也可能是排除所有未来的问题实例，而如果解决方案变为 "NO"，则有必要在解决方案中保留此组合。）
给定 3DM 的实例 (X, Y, Z, T, k)，其中 X、Y 和 Z 是彼此成对不相交的集合，T 是 X*Y*Z 的子集（即，一组有序的三元组，分别具有来自 X、Y 和 Z 的第一、第二和第三分量）并且 k 是一个整数，我们的任务是确定是否存在 T 的任何子集 U 使得 |U| >= k 并且 U 中的所有三元组都是成对不相交的（即，回答问题，"Are there at least k non-overlapping triples in T?"）。要将 3DM 的任何此类实例变成您的问题的实例，我们需要做的就是通过为每个三元组添加不同的虚拟值，从 T 中的每个三元组创建一个新的 4 组合。问题的构造实例中的对象集将由 X、Y、Z 和 |T| 的并集组成我们创建的虚拟值。最后，将m设置为k。
假设原始3DM实例的答案是"YES"，即T中至少有k个non-overlapping个三元组，那么这个解中的k个三元组中的每一个都对应一个输入 C 中的 4 组合到您的问题，并且这些 4 组合中没有两个重叠，因为通过构造，它们的第 4 个元素都是不同的，并且假设。因此，在您的问题实例中至少有 m = k non-overlapping 4 种组合，因此该问题的解决方案也必须是 "YES".
在另一个方向上，假设您的问题的构造实例的解决方案是 "YES"，即 C 中至少有 m non-overlapping 个 4-组合。我们可以简单地取每个 4 组合的前 3 个元素（丢弃第四个）产生一组 k = m non-overlapping T 中的三元组，因此原始 3DM 实例的答案也必须是 "YES" .
我们已经证明，一个问题的 YES-answer 意味着另一个问题的 YES-answer，因此一个问题的 NO-answer 意味着另一个问题的 NO-answer。因此问题是等价的。您的问题实例显然可以在多项式时间和 space 中构造。由此可见，您的问题是 NP-hard.