找出重新组合的 m 个给定集合中的最小 nr 的最快方法包括单独的 m+1 集合
下面给出了一个实际的例子：
假设m = 4：
// the sets for reuniting
Set1 = { 5 , 1 , 2 }
Set2 = { 2 , 6 , 3 }
Set3 = { 7 , 8 , 4 }
Set4 = { 4 , 9 , 10}
// the set I need to form
Set m+1: Set5 = { 1 , 2 , 3 , 4 }
我必须找到一组索引，例如A = { 1, 2, 3 }，以便U (Seti) 包括 Set5，其中 i 是 A 的一部分。 A 的基数必须是最小的。
The following gives a practical example:
Let's say for m = 4:
// the sets for reuniting
Set1 = { 5 , 1 , 2 }
Set2 = { 2 , 6 , 3 }
Set3 = { 7 , 8 , 4 }
Set4 = { 4 , 9 , 10}
// the set I need to form
Set m+1: Set5 = { 1 , 2 , 3 , 4 }
I have to find a set of indexes e.g. A = { 1, 2, 3 } so that U (Seti) includes Set5, where i is part of A. The cardinal of A must be minimal.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
如果我正确理解你的问题，
这就是集合覆盖问题，这是NP难的。
因此，不存在既是最优又是贪婪的算法。查看显示贪婪次优方法的文章。
If I understood your question correctly,
this is the set cover problem, which is NP hard.
As a consequence, there is no algorithm which is both optimal and greedy. Check the article which shows a greedy suboptimal approach.
如果我正确地理解了这个问题，这里的伪代码返回覆盖 set5 的集合的索引：
请注意，这是一种贪婪的方法，并且不能保证 A 是最小的
if i understood the problem correctly, here's pseudo code that returns the indexes of the sets that cover set5:
notice that it's a greedy approach and doesn't guarantee A being minimal