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

Question

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

ex. 1 2 3 8 10 4

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

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

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

Answer 1

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

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

Answer 2

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

Answer 3

Просто придав ему некоторые действительно короткую мысль:

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