算法问题：n个集合中取m个集合，可以包含最多的元素

n个集合（任意两个集合可能都有公共元素）中取m个集合，可以包含最多的元素……
应该不是一个动态规划问题，应该有相关的算法描述这类问题

有知道的吗？描述下…，最好是高效的

8 个解决方案

#1

？
？………

#2

没有人知道吗？？

#3

只想到最简单的方法，直接用贪心思想解决，先从n个集合中找到元素最多的一个集合，加入答案集合A，对余下的n-1个集合，都去除掉A集合中的元素，然后再从n-1个集合中找到元素最多的一个集合，加入答案集合A。依次。。。。直接已经选择m个集合或去除过程中，剩余的集合为空。

#4

引用 3 楼 allen_lxs 的回复:

只想到最简单的方法，直接用贪心思想解决，先从n个集合中找到元素最多的一个集合，加入答案集合A，对余下的n-1个集合，都去除掉A集合中的元素，然后再从n-1个集合中找到元素最多的一个集合，加入答案集合A。依次。。。。直接已经选择m个集合或去除过程中，剩余的集合为空。

大概不行，假定取3个 ，（1,2,3),(4,5,6)(789)(134689)，只要你第一个取了集合4，就肯定找不到正解

#5

嗯，不是贪心算法问题

有如下想法：是不是没有专业的名字来描述这个问题

可以用回溯法，暴力法解决，关键是如何设计数据结构或预处理，降低复杂度

还有好的想法吗？

#6

优先选取集合元素个数较多的？两两集合交集小的？

#7

现在关键是在数据结构和算法上做优化了…

另外有什么论文提到过这类问题吗？

我引用一下就可以了……

#8

Maximum coverage problem问题！

The maximum coverage problem is NP-hard！

http://en.wikipedia.org/wiki/Maximum_coverage_problem