python - 精确覆盖问题，但对解决方案中子集的精确数量有限制

Question

我对精确覆盖和类似问题相对较新，所以请多多包涵。假设我有一个典型的精确覆盖问题，即。给定一组X和一组X的子集S，我想找到完全覆盖X的S * （ S 的子集）。但是，我希望解决方案S * 恰好包含k 个元素。此外，一种解决方案就足够了。

我知道 Knuth 的算法 X 旨在返回所有可能的解决方案。我应该只运行 Knuth 的算法并遍历解决方案，直到找到具有k个元素的解决方案，还是（我怀疑）有更好的方法？我正在使用 Python 顺便说一句。

对于上下文，X的大小 <100 但S的大小可以是 10^6。k在 <10 时相对较小。

标签： pythonalgorithmperformancenp-completeknuth

Answer 1

如果k很小，您可以简单地尝试添加k额外元素，并复制每个子集k时间，每个副本都包含一个k额外元素。

另一种方法是将精确覆盖问题作为整数线性程序求解，并使用 ILP 求解器求解。然后，您将有 0-1 个变量x_i来说明i第 th 子集是否包含在解决方案中，并具有防止重叠集包含在解决方案中的约束。在这个公式中，为了提供一个完全包含k子集的覆盖，您只需有一个额外的约束sum(x_i) = k.

也可以修改算法 X 以直接处理约束。只需计算到目前为止您选择了多少行，如果您已经选择了k，则直接失败，无需进一步搜索。同样，忽略行数少于的解决方案k。