s********s
发帖数: 4011 | 1 最近遇到个问题，忘了有没有相关算法了。
有一些set, from A1 to An, each set contains a number of elements
Ai and Aj has intersection. 比如 Ai=(1,2,3,4) Aj=(3,4,7,8,9,10).
How to find the minimum number of sets from A1 to An so that
Union of these sets = Union of A1 ... An
Thanks. | sc
发帖数: 122 | 2 我不知道是不是有现成的算法，
不过想了一个，不知道好使不好使，
有数组B(1..M)，
初始话：
建个可以反查的质数表P(i)
loop i
loop A_i(j)
k=A_i(j)
如果B(k)没值，B(k)=P(i)
否则B(k)=B(k)*P(i)
end loop
end loop
然后扫描数组B，是质数，说明stand alone，这个质数对应的set要得，
然后用这个质数除B里的每一个可以整除的元素。
一直搞一直搞，搞到它剩下一堆1和一堆合数，
然后找最小公约数什么的。
整个过程有点烦，不知道有没有简单的。
【在 s********s 的大作中提到】
: 最近遇到个问题，忘了有没有相关算法了。
: 有一些set, from A1 to An, each set contains a number of elements
: Ai and Aj has intersection. 比如 Ai=(1,2,3,4) Aj=(3,4,7,8,9,10).
: How to find the minimum number of sets from A1 to An so that
: Union of these sets = Union of A1 ... An
: Thanks.
| l*******g
发帖数: 17 | 3 http://en.wikipedia.org/wiki/Set_cover_problem
this is called "set covering problem", and is NP-complete
【在 s********s 的大作中提到】
: 最近遇到个问题，忘了有没有相关算法了。
: 有一些set, from A1 to An, each set contains a number of elements
: Ai and Aj has intersection. 比如 Ai=(1,2,3,4) Aj=(3,4,7,8,9,10).
: How to find the minimum number of sets from A1 to An so that
: Union of these sets = Union of A1 ... An
: Thanks.
|
|
