集合覆盖问题除了贪婪法,还有其他的解法吗,就是比较常见的解法,比如递归法或者动态规划算法
给定全集 ,以及一个包含n个集合且这n集合的并集为全集的集合 。集合覆盖问题要找到 的一个最小的子集,使得他们的并集等于全集。
例如 , ,虽然 中所有元素的并集是 },但是我们可以找到 的一个子集 ,我们称其为一个集合覆盖。
形式化的定义,给定全集 和他的一组子集组成的集合 ,覆盖指一个集合 且C的元素的并集为 。
集合覆盖问题的决定性问题为,给定 和一个整数k,求是否存在一个大小不超过k的覆盖。集合覆盖的最佳化问题为给定 ,求使用最少的集合的一个覆盖。