从包含m的文件中选择n个JavaScript函数的Python和Django高效算法

Question

我需要一个高效的Python算法来满足以下需求。在

假设我在一个文件中有N个JavaScript函数。我必须以任何特定的顺序在N中包含任何M JavaScript。（例如，在一个页面中，I可能包括N1、N4、N5、N6和另一个页面N1、N5、N4、N3，但是应该以相同的顺序包含它。）

什么是有效的方法？在

Answer 1

这被称为maximum coverage problem，是NP-Hard（非确定性多项式时间困难）。。。然而，确实存在一些近似算法，最容易实现的是基于贪婪的算法。在

假设你需要包括一个。。。多个JavaScript文件。您需要根据JavaScript代码包含的这些元素的数量来对其进行排序，并在每次迭代时重新计算它们的权重。在

简单示例：

• JavaScript1有[n1，n2，n3，n5]
• JavaScript2有[h1，h2，n4]
• JavaScript3有[n4，n6]

假设您要包括n_1…n_6。您将对这些JavaScript文件进行排序，使原始排序为[JavaScript1，JavaScript2，JavaScript3]（按照它们提供的覆盖率的顺序）。您将首先使用JavaScript1，现在只需要n4和n6。。。如果您根据能够提供最多覆盖率的JavaScript文件调用其余的JavaScript文件，那么新的顺序将是[JavaScript3，JavaScript2]。请注意，尽管第二个文件包含更多的定义，但JavaScript3更有用，因为它将覆盖其余未覆盖的定义。在

你可以自己写算法！：）