给定一个单词列表和一个最多有P个字母的字母表，我们如何选择涵盖最多单词的最佳字母？
例如：给定单词“aaaaaa”“bb”“bb”，其中P = 1，最佳字母表是“b”，因为“b”包括两个单词。
另一个例子：给出单词“abmm”“abaa”“mnab”“bbcc”“mnnn”，其中P = 4，最佳字母表是“abmn”，因为它覆盖了5个单词中的4个。
有没有已知的算法，或者有人建议解决这个问题的算法？
给定一个单词列表和一个最多有P个字母的字母表，我们如何选择涵盖最多单词的最佳字母？
例如：给定单词“aaaaaa”“bb”“bb”，其中P = 1，最佳字母表是“b”，因为“b”包括两个单词。
另一个例子：给出单词“abmm”“abaa”“mnab”“bbcc”“mnnn”，其中P = 4，最佳字母表是“abmn”，因为它覆盖了5个单词中的4个。
有没有已知的算法，或者有人建议解决这个问题的算法？
从CLIQUE（它是一种最密集的k-sub（超）图问题）减少这个问题是NP难的。给定一个图形，用不同的字母标记其顶点，并为每个边缘创建一个两个字母的单词。当且仅当我们能够覆盖k选择2个单词和k个字母时，才存在k-clique。
CLIQUE的算法情况是 严峻 （在合理的假设下，运行时间必须是n ^ Theta（k）），所以我不确定除了蛮力与原始之外还要推荐什么 位数组。
我还不确定这是否正确，但希望它至少接近。我们考虑动态编程解决方案。枚举单词1到N，我们的字母表1到P中的字母。我们希望能够根据所有子解决方案求解（n，p）。我们考虑几个案例。
最简单的情况是第n个单词已经在（n-1，p）的解决方案中给出的字典中。然后我们将自己算作幸运，用一个词覆盖，并保持字典不变（ddictionary指的是这里的一些字母子集）。
相反，假设第n个单词不在（n-1，p）给出的字典中。然后字典求解（n-1，p）是（n，p）的字典，或者第n个字在解决方案中。因此，我们寻找明确涉及第n个单词的解决方案。因此，我们将第n个单词中的所有字母添加到我们正在考虑的字典中。我们现在搜索表格（n-1，i）的所有先前的子集，其中i是p-1或更小。我们正在寻找i的最大值，使得| d（n-1，i）U d（n）| <= p。其中d（n-1，i）表示与该解决方案相关联的字典，而d（n）仅表示与第n个单词的所有字母相关联的字典。用简单的英语，我们使用我们的子解决方案来找到具有较小p值的最佳解决方案，这允许我们适应新单词。一旦我们找到了i的值，我们就会结合我们测量的大小的字典。如果该集合的幅度仍然不是p，我们重复前面描述的过程。当我们创建一个大小为p的字典，用这种技术覆盖第n个单词（或通过所有先前的解决方案迭代），我们计算其覆盖范围并将其与我们通过简单地使用来自（n-1， p），我们选择更好。如果这是一个平局，我们选择两者。
我不完全相信这个解决方案的正确性，但我认为这可能是正确的。思考？
我这样做：
正如大卫在上面所展示的那样（有一个很好的证明！），这是NP难的，所以你不会在任何情况下得到完美的答案。
添加到其他答案的一种方法是将其表达为最大流量问题。
定义源节点S，汇聚节点D，每个字的节点以及每个字母的节点。
将S中的边添加到容量1的每个字中。
将每个单词的边添加到包含无限容量的字母。
将每个字母的边添加到容量x的D（我们将在片刻中定义x）。
然后求解该图的最小切割（通过使用从S到D的最大流算法）。字母的切边表示该字母未包含在解决方案中。
这可以被认为解决了我们每个单词获得1的奖励的问题，但是对于我们使用的每个新单词，它花费我们x。
然后，想法是改变x（例如通过二分法）以试图找到x的值，其中恰好切割k个字母边缘。如果您对此进行了管理，那么您将确定问题的确切解决方案。
这种方法相当有效，但它取决于您的输入数据是否能找到答案。对于某些例子（例如大卫的构造来寻找派系），你会发现当你改变x时，你会突然从少于k个字母跳到包括多个k个字母。但是，即使在这种情况下，您可能会发现它有助于为精确解中的最大字数提供一些下限和上限。