Проблема с балансировкой гальки

Question

Я сталкивался с этой проблемой раньше, это проблема балансировки. Программа принимает массив целых чисел размера n. Затем программа определяет, можно ли разбить этот массив целых чисел на 2 равные части, при этом суммы целых чисел в каждой половине равны.

ех. 1 2 3 8 10 4

, в котором программа возвращает true, что означает, что ее можно разбить на две половины по 14 в каждой

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

Пошаговое решение будет очень полезно. Большое спасибо

Answer 1

Просто немного подумав:

• Проблема эквивалентна поиску любого подмножества гальки, которая весит ровно половину от общего веса гальки
• Если самая тяжелая галька весит большечем половина общего веса гальки, нет решения

Answer 2

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

Вы можете легко проверить все возможные способы: для каждого элемента он находится либо в левой половине, либо в правой половине.

Answer 3

Посмотрите на мой ответ для этой проблемы. Ваша проблема существенно связана. Вы должны найти, какие суммы вы можете получить с помощью чисел. Если сумма: total_sum / 2 может быть достигнута, значит, вы нашли решение:)