集合覆盖问题

集合覆盖问题（ Set covering problem，SCP）是组合数学、计算机科学和计算复杂性理论中的一个经典问题。

集合覆盖的决定性问题是卡普的二十一个NP-完全问题之一。

给定全集${\displaystyle \mathcal{U}}$指一个集合${\displaystyle \mathcal{C}}$，${\displaystyle \mathcal{C}\subseteq <!--\; \subseteq \; -->\mathcal{S}}$，且${\displaystyle \mathcal{C}}$的元素的并集为${\displaystyle \mathcal{U}}$。

集合覆盖问题的决定性问题为，给定${\displaystyle (\mathcal{U},\mathcal{S})}$和一个整数${\displaystyle k}$，求是否存在一个大小不超过${\displaystyle k}$的覆盖。集合覆盖的最佳化问题为给定${\displaystyle (\mathcal{U},\mathcal{S})}$，求使用最少的集合的一个覆盖。

决定性问题的集合覆盖是NP完全问题，最佳化问题的集合覆盖是NP困难问题。

此外，问题可以在每个集合上添加权值而变为带权集合覆盖问题。