Я тут вспомнил, что у меня осталась ещё одна не реализованная идея. Я как-то размышлял над тем, нельзя ли применить в этой задаче парадигму "разделяй и властвуй". Этот подход позволяет заменить линейный множитель в сложности алгоритма на логарифмический. Конкретно в этой задаче, если от экспоненциальной сложности удастся отщепить экспоненциальный множитель и заменить его на линейный, то, не смотря на то, что алгоритм всё равно останется экспоненциально сложным, его сложность упадёт неимоверно (хочется на это надеяться во всяком случае).
Идея заключается в том, чтобы разбить множество целевых сумм на два равных или близких по количеству. Важно, чтобы близких именно по количеству, а не по величине! Потому что чем больше различие по величине, тем лучше (меньше потенциальных вариантов перебора). Внутри этих двух множеств сумм подсчитывается сумма. Получается два числа. Это новые целевые суммы самого верхнего уровня алгоритма. Теперь надо найти такое разбиение исходное множества элементов, чтобы получались эти две суммы. Задача уже решена ранее. Таких разбиений будет очень много. И в них будет очень мало тех, которые ведут к решению. Именно это меня и остановило использовать эту идею.
Рассмотрим конкретный пример:
[9, 14, 34, 42, 47, 49, 57, 66, 68, 71, 74, 97, 100]
[5, 2, 5, 5, 1, 1, 1, 1, 4, 5, 2, 7, 10]
[227, 235, 264, 292, 298, 322, 327, 341, 820]
0: 227 -> 96
1: 235 -> 107
2: 264 -> 179
3: 292 -> 279
4: 298 -> 305
5: 322 -> 431
6: 327 -> 459
7: 341 -> 555
8: 820 -> 20314
9: 462 -> 2129
10: 726 -> 13379
11: 1018 -> 37779
12: 1316 -> 62229
13: 1638 -> 69566
14: 1965 -> 50622
15: 2306 -> 20314
16: 3126 -> 1Здесь в первой строчке уникальные значения элементов, во второй — количество повторов каждого элемента, в третьей — целевые суммы. Затем для некоторых чисел (которые являются целевыми суммами и суммами целевых сумм) посчитано число решений, которыми каждое это число можно представить через исходное множество элементов. Видно, что для числа 1018, являющимся суммой наименьших четырёх сумм число решений чуть меньше 38 тысяч. Это не большое число само по себе, но не надо забывать, что это только первый уровень алгоритма!
После получения одного решения для двух сумм подмножеств сумм, проверяется существует ли решение (выполнение отсечений) для каждой суммы, входящей в сумму, но уже со значительно меньшим числом элементов исходного множества (в лучшем случае с половиной). Если для обоих разбиений все суммы разрешимы, то алгоритм спускается на уровень вниз и по очереди решает задачу для подмножеств сумм и подмножеств элементов. Если в обоих случаях находится решение, то конечное решение комбинируется из частичных и алгоритм возвращается наверх с успехом. Если произошло отсечение или же хотя бы одно решение вернулось с нижележащего уровня с неудачей, то пробуется следующее разбиение на текущем уровне. Если все варианты перебраны, то возвращаемся наверх с неудачей.
Алгоритм выходит рекурсивный, по другому просто не знаю как это реализовать. Я понимаю, что любая рекурсия развёртывается, но не всегда это рационально. Погружение производится, пока не останется две суммы, для которых просто ищется решение. В случае, если на входе алгоритма было всего две суммы, то погружаться вообще не надо. В случае, если было три суммы, то происходит просто отщепление одной, потом проверка и погружение.
Сложность алгоритма всё равно останется довольно таки заметной. Конкретно для этого теста на первом этапе получается 37779 комбинаций. На втором для каждой из половинок получится меньше, но тоже заметное число. Пусть где-то 2129 (вариант с числом решений для двух сумм, но с полным числом элементов — оценка сверху с запасом). На третьем уровне будет где-нибудь по 100-200 комбинаций. В итоге получается произведение порядка
. Остаётся надеяться, что решение найдётся значительно раньше, чем перебор хотя бы 1% этих вариантов. Плюс отсечения сделают своё благое дело.