algorithm - k 个元素的最大集覆盖集

Question

给定元素 U={e_1....e_n} 的宇宙，我有这些元素的子集 C={s_1...s_m} 的集合。现在给定一个正整数 k，我想找到包含最大子集数的 k 个元素的解。

一个具体的例子:我有一个歌曲集。每首歌都是由音符组成的。如果我只知道如何弹奏 k 个不同的音符 - 哪 k 个音符可以让我弹奏最大数量的歌曲，这个最大数量是多少？

这个问题怎么称呼？

Answer 1

蛮力法:

首先从 n 中找出大小为 k 的所有不同排列。然后对于每个排列找到它覆盖的子集数。请记住，例如，如果您采用覆盖子集“s_1”的一个元素，那么您必须从该子集中获取所有元素，否则贪婪方法将仅覆盖子集的一部分而不是整个子集。然后选择给出最大答案的排列。

但蛮力方法仅在 k 小于 10 时有效。由于订单呈指数增长，没有比这更好的解决方案，因此这个问题转到 np_hard。可以证明您的问题已简化为顶点覆盖问题。

将子集视为树，将元素视为节点。现在你的问题是选择 k 个元素，使其完全覆盖最大数量的树。