Найти 2 списки равной суммы из большего списка

Question

Ok поэтому в основном у меня есть список или массив целых чисел

List = (1,3,22,17,22,4,15,40)

И мне нужно найти два списка, как это:

List1 = (1,3,17,4,15,22) ... Sum = 62

List2 = (22,40). .. Сумма = 62

Все целые числа должны использоваться, целое число должно быть в List1 или List2

---- моя первая мысль ----

Choose the largest nb i.e 40 and try to find integers equal to 40 and add 
to the second list ... But that's not the way ... 

, приведенный выше список является примером список ... Я должен быть в состоянии найти List1 и List2, если это возможно для любого заданного списка.

Answer 1

Первый шаг - найти сумму всех элементов списка. Это будет в два раза больше суммы двух подписок, которые вы ищете. Используя ваш пример, сумма (1,3,22,17,22,4,15,40) равна 124, что вдвое превышает 62.

Итак, теперь вы ищете набор чисел в пределах список, который суммируется до 62. Вам не нужно беспокоиться о поиске двух наборов (если вы его найдете, остальные цифры обязательно составят 62). Я бы сделал это алгоритмически - сначала найдите набор размеров 1, чьи элементы суммируются до 62 (т. Е. Просматривают список и проверяют, есть ли какое-либо число 62). Если такое число существует, все готово. Если нет, то посмотрите на наборы размеров 2. Это сложно, потому что вам придется посмотреть на все возможные комбинации. Поскольку у вас 7 чисел, есть (7 * 6)/2 = 21 возможности. Если любой из них - 62, все готово. Если нет, переходите к проверке наборов размера 3. И так далее, пока не достигнете размера 7/2 (в этом случае вы делаете 3 в этом случае). Очевидно, что с большими наборами этот процесс будет включать в себя множество вычислений и сравнения; его можно оптимизировать с помощью нескольких ярлыков, но основной алгоритм один и тот же.

Если в итоге не найдены подмножества, суммирующие до 62, это потому, что таких подмножеств не существует.

Answer 2

В общем, ваша проблема связана с NP-трудностью, что означает, что, по мере роста размера массива n, вероятно, не существует быстрого решения (полиномиальное время). Однако, если ваши числа являются относительно небольшими целыми числами (что означает, что сумма их абсолютных значений составляет порядка 1 миллиарда или 10 миллиардов или менее в зависимости от того, сколько у вас памяти), вы можете использовать динамическое программирование. В основном для первых k элементов вашего массива вы сохраняете все возможные суммы, которые вы можете сделать с помощью подмножеств этих k элементов. Вы увеличиваете k постепенно, беря все суммы, образованные подмножествами первых k элементов, а затем добавляя (k + 1) -й элемент вашего массива или нет, что увеличивает набор доступных сумм. Предполагая, что ваши n чисел являются целыми числами, общая сложность этого подхода - O (nM), где M - общая сумма абсолютных значений элементов в вашем массиве. Если у вас закончилась нехватка памяти, вы можете использовать дисковое пространство для хранения доступных подмножеств, но это сделает время работы медленнее, очевидно; однако, используя дисковое пространство, вы можете обрабатывать массивы чисел, абсолютные значения которых составляют порядка 1 триллиона или более в зависимости от того, сколько дискового пространства у вас есть.