Проблема с балансировкой гальки
Я сталкивался с этой проблемой раньше, это проблема баланса. Программа принимает массив целых чисел размера n. Затем программа определяет, можно ли разбить этот массив целых чисел на 2 равные части, при этом суммы целых чисел в каждой половине равны.
ех. 1 2 3 8 10 4
в котором программа возвращает true, то есть ее можно разбить на две половины по 14 в каждой
Я знаю, что это касается комбинаций / перестановок, и я не очень хорош в них. Мне только удалось подумать о методе грубой силы. Можно ли это решить с помощью любых других методов? может быть, более эффективные алгоритмы?
Пошаговое решение будет очень полезно. большое спасибо
3 ответа
Это проблема разбиения, которую можно легко увидеть эквивалентной задаче суммы подмножеств и задаче о ранце. Это NP-Complete, и считается, что вы не можете добиться значительно лучше, чем исчерпывающий список всех комбинаций.
Вы можете легко проверить все возможные способы: для каждого элемента он находится либо в левой, либо в правой половине.
Просто немного подумав:
- Эта проблема эквивалентна поиску любого подмножества гальки, которое весит ровно половину от общего веса гальки
- Если самая тяжелая галька весит больше половины общего веса гальки, решения не существует
Посмотрите на мой ответ для этой проблемы. Ваша проблема существенно связана. Вы должны найти, какие суммы вы можете получить с помощью чисел. Если сумма: total_sum / 2 может быть достигнуто, то вы нашли решение:)