Эффективный алгоритм в Python и Django для выбора n функций JavaScript из файла, содержащего m

Question

Мне нужен эффективный алгоритм в Python для следующего требования.

Рассмотрим, что у меня в файле N функций JavaScript.Я должен включить любой M JavaScript среди N в любом конкретном порядке.(Например, на одной странице я могу включить N1, N4, N5, N6 и другую страницу N1, N5, N4, N3, но она должна быть включена в том же порядке.)

Что является эффективным способомсделать это?

Answer 1

Это известно как проблема максимального покрытия , и NP-Hard (недетерминированный полиномиальный хард) ... Однако существуют некоторые алгоритмы аппроксимации проще всего реализовать алгоритм на основе жадных алгоритмов.

Скажем, вам нужно включить N_1 ... N_m файлы 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, основанным на тех, которые обеспечат наибольшее покрытие, новый порядок будет [JavaScript3, JavaScript2]. Обратите внимание, что хотя второй файл содержит больше определений, JavaScript3 более полезен, поскольку он будет охватывать оставшиеся непокрытые определения.

Вы можете сами написать алгоритм! :)