我对精确覆盖和类似问题相对较新，所以请耐心等待。假设我有一个典型的精确覆盖问题，即。给定一个集合X 和一个 X 的子集 S 的集合，我想找到精确覆盖X的 S*(S的子集(。但是，我希望解决方案S* 正好包含k个元素。而且，一个解决方案就足够了。
我知道高德纳的算法X旨在返回所有可能的解决方案。我应该运行 Knuth 算法并迭代解决方案，直到找到一个包含k个元素的解决方案，还是(正如我怀疑的那样(有更好的方法？顺便说一句，我正在使用Python。
对于上下文，X的大小为 <100，但S的大小可以是 10^6。k相对较小，为 <10。
如果k很小，您可以简单地尝试添加k个额外的元素，并将每个子集复制k次，每个重复只包括一个k额外的元素。
另一种方法是将确切的覆盖问题作为整数线性规划求解，并使用 ILP 求解器求解。然后，您将有 0-1 个变量x_i，用于说明解决方案中是否包含第i个子集，以及防止解决方案中包含重叠集的约束。在此公式中，要提供具有正好k子集的覆盖，您只需具有sum(x_i) = k的附加约束。
还可以修改算法 X 以直接处理约束。只需计算到目前为止您选择了多少行，如果您已经选择了k，则无需进一步搜索即可失败。同样，忽略少于k行的解决方案。