Задача о суммировании подмножеств, решенная за линейное время при достаточно высокой плотности входных данных.

Оптимальное решение известной NP-полной задачи, когда входные значения достаточно близки друг к другу.

Делиться

В этой статье я представлю решение задачи суммирования подмножеств, имеющее линейную временную сложность O(n), если все 'n' входных значений достаточно близки друг к другу. Вскоре мы увидим, что на самом деле означает это условие, а также почему его часто можно соблюдать (или почти соблюдать) на практике. Для входных данных, которые «почти близки» друг к другу, алгоритм все еще имеет определенную вероятность работать достаточно быстро.

Данная статья построена следующим образом:

• В главе 1 мы вспомним задачу о сумме подмножеств и покажем, вероятно, наиболее тривиальное решение этой задачи, основанное на методе полного перебора.
• В главе 2 рассматривается класс NP-полных задач и связь задачи о сумме подмножеств с ним.
• В главе 3 рассматривается широко используемое решение, основанное на методе динамического программирования, и объясняется, почему это псевдополиномиальный алгоритм.
• В главе 4 я представлю новый алгоритм, называемый «Решение на основе интервалов».
• В главе 5 будет показано, что, подобно методу динамического программирования, алгоритм, основанный на интервалах, также может восстановить точное подмножество элементов, формирующих заданную целевую сумму, а не просто ответить, достижима ли целевая сумма или нет.
• Наконец, в главе 6 мы увидим, почему алгоритм, основанный на интервалах, фактически достигает линейной временной сложности, если все 'n' входных значений достаточно близки друг к другу (а также мы поймем, что на самом деле означает условие «достаточно близки»).

Источник: towardsdatascience.com