алгоритм равных k подмножеств

Question

Кто-нибудь знает хороший и эффективный алгоритм для алгоритма равных k подмножеств?предпочтительно c или c ++, который может обрабатывать вектор из 100 элементов, может быть с оценкой сложности и времени

ex.9-элементный вектор

x = {2,4,5,6,8,9,11,13,14}

мне нужно сгенерировать все k = 3 непересекающихся подмножеств с суммой = 24алгоритм должен проверить, есть ли k непересекающихся подмножеств, каждое с суммой элементов 24, и перечислить их в порядке возрастания (в подмножестве и между подмножествами) или посмотреть, не существует ли решение

Решения

решение 1: {2 8 14} {4 9 11} {5 6 13}

решение 2: {2 9 13} {4 6 14} {5 8 11}

Спасибо

Answer 1

К сожалению, проблема ограниченного k-подмножества является сложной проблемой ... и если вы хотите сгенерировать все таких k-подмножеств, у вас нет выбора, кроме как оцените множество возможных кандидатов .

Существует несколько оптимизаций, которые можно выполнить, чтобы уменьшить пространство поиска.

Учитывая домен x, содержащий целочисленные значения, Учитывая положительное целое число M, Учитывая положительное целое число k для подмножества,

1. Если x содержит только положительные целые числа и задана верхняя граница M, удалите все элементы из x больше или равного M. Они не могут быть частью подмножества.
2. Аналогично, для k> 1, данного M и x, содержащего натуральные числа, удаляются все элементы из x, которые больше, чем M + min0 + min1 ... minK. По сути, удалите все большие значения, которые, возможно, не могут быть частью подмножества, поскольку даже при выборе небольших значений они приведут к сумме, превышающей M.
3. Вы также можете использовать принцип четного / нечетного исключения, чтобы сократить пространство поиска. Например, если k нечетно, а M четно, вы знаете, что сумма будет содержать три четных числа или два нечетных и одно четное. Вы можете использовать эту информацию, чтобы уменьшить пространство поиска, исключив значения кандидатов из x, которые могут быть частью суммы.
4. Сортировать вектор x - это позволяет быстро исключить значения, которые невозможно включить в сумму.

Многие из этих оптимизаций (кроме четного / нечетного исключения) больше не используются / действительны, когда вектор x содержит отрицательные значения. В этом случае вам, скорее всего, придется провести исчерпывающий поиск.

Как отмечает Jilles De Wit , если X содержит отрицательные числа, вы можете добавить абсолютное значение наименьшего значения в X к каждому члену X. Это сместит все значения обратно в положительный диапазон - делая некоторые из описанных выше оптимизаций возможны снова. Это требует, однако, чтобы вы могли точно представлять положительные значения в расширенном диапазоне. Одним из способов достижения этого является внутреннее использование более широкого типа (скажем, long вместо int) для выполнения поиска выбора подмножества. Однако, если вы сделаете это, не забывайте масштабировать подмножества результатов обратно на это же смещение при возврате результатов.