我想提取数据帧的最小行数以覆盖某些列的所有元素。 这是一个例子：
在此处输入图像描述
条件： 新数据帧的清单1封面(A，B，C);新数据帧的清单2封面(阿尔法、贝塔、德尔塔、伽玛);新数据帧的project_id封面(PROJ1、ProJ2、PROJ3);
溶液：
在此处输入图像描述
我试图通过枚举解决这个问题。最后，我放弃了这种方法进行大量计算。
此问题是众所周知的集合覆盖问题的变体。
由于这个问题是NP完全的，如果输入不是很小，找到一个最佳解决方案(意味着在您的例子中，行中将涵盖所有值的最小元素量)可能需要大量时间。否则，这个问题的复杂性在输入大小方面是指数级的(O(2^n)，行数n，或多或少)。
但不要失去希望，有些方法可以让您在输入很小的情况下找到最佳解决方案，或者如果您的输入很大，则可以找到非常令人满意的近似值。通过小输入，我的意思是或多或少为 100 数量级的行数。
分支和绑定：这种算法或多或少是一种"聪明"的蛮力方式，它的运行速度比蛮力算法快得多。它可以找到一个最佳解决方案(如果有足够的时间，如果输入很大，足够的时间可能意味着一百万年)，或者它可以停止并返回迄今为止找到的最佳解决方案。我不建议您使用这种方法，但您绝对应该阅读它，它是一种非常高效且通用的算法，必须知道。
整数线性规划：恕我直言，这是解决这个问题的最佳方法。ILP 允许您将程序编写为整数线性程序，然后将其馈送到 ILP 求解器(市场上有很多，免费与否，您可以在此处找到列表)。如果您从未听说过线性规划，可以在此处查看一些解释。
这种方法有两个很大的优势：
- 编写一个可以解决集合覆盖问题的 ILP 程序非常容易，正如你在这里看到的(最多十几行)。
- ILP求解器非常优化，它们是专门为解决此类问题而编写的。如果您的输入小于(例如 1000 行)，它应该找到最佳解决方案。而且，无论如何，它将找到比几乎任何程序更好的解决方案。至少，这是一个比你花不到一周时间编写的程序更好的解决方案。
总是有可能采用贪婪算法，但集合覆盖问题不能用多项式时间算法近似(这是对事实的过度简化，但在我们的例子中已经足够了，我们想解决集合覆盖的实例，而不是证明 P=NP 或研究独特的游戏猜想)。因此，贪婪算法的结果可能比最优解差得多。并且运行速度仅比更好的 ILP 求解器略快。