Разделение массива по равенству двух частей
1,00
р.
Как разделить массив на две равные части, суммы элементов которых наиболее близки к равенству.
Как разделить массив по на две части, я знаю. Но не могу придумать, как сделать? чтобы суммы элементов этих двух частей были равны. Прошу подсказать алгоритм.
Для тех, кто просил уточнить условие: массив делится на две равные части, количество элементов первой части = количеству элементов второй. Также сумма элементов первой части равна или наиболее близка к равенству второй части.
Ответ
Вы переформулировали так называемую Partition Problem. Это известная Weakly NP-Complete задача, для которой существует псевдополиномиальный алгоритм и примерный полиномиальный алгоритм.
Подробнее можете почитать, пройдя по первой ссылке или, например, здесь: Divide list in two parts that their sum is closest to each other.
Если вас устроит примерное решение, то используйте O(N log N) жадный алгоритм
(Для тех, кто сидит в комментариях :)
Условие деления массива на части одинаковой длины не влияет на NP-полноту задачи (она все еще NPC). Доказательство этого факта с точки зрения теории алгоритмов может звучать примерно так:
Сведем общую задачу Partition Problem (PP) к задаче с двумя равными частями Equally Sized Partition Problem (ESPP), то есть покажем, что ESPP включает в качестве частного случая задачу PP.
Рассмотрим последовательность элементов длиной 2k, из которых k являются нулями. Теперь, решив эту задачу с помощью алгоритма ESPP, мы получим две последовательности длины k, разница сумм которых минимальна. Поскольку нулевые элементы не меняют суммы, то мы можем "перегнать" их из одной последовательности в другую, соответственно, сводя задачу к PP.
Раз мы доказали, что задача NPC, то полиномиального алгоритма решения этой задачи не существует. Можете воспользоваться псевдополиномиальным алгоритмом из википедии, адаптировав его для себя или любым жадным алгоритмом из тех, что предложен ниже.
Как разделить массив по на две части, я знаю. Но не могу придумать, как сделать? чтобы суммы элементов этих двух частей были равны. Прошу подсказать алгоритм.
Для тех, кто просил уточнить условие: массив делится на две равные части, количество элементов первой части = количеству элементов второй. Также сумма элементов первой части равна или наиболее близка к равенству второй части.
Ответ
Вы переформулировали так называемую Partition Problem. Это известная Weakly NP-Complete задача, для которой существует псевдополиномиальный алгоритм и примерный полиномиальный алгоритм.
Подробнее можете почитать, пройдя по первой ссылке или, например, здесь: Divide list in two parts that their sum is closest to each other.
Если вас устроит примерное решение, то используйте O(N log N) жадный алгоритм
(Для тех, кто сидит в комментариях :)
Условие деления массива на части одинаковой длины не влияет на NP-полноту задачи (она все еще NPC). Доказательство этого факта с точки зрения теории алгоритмов может звучать примерно так:
Сведем общую задачу Partition Problem (PP) к задаче с двумя равными частями Equally Sized Partition Problem (ESPP), то есть покажем, что ESPP включает в качестве частного случая задачу PP.
Рассмотрим последовательность элементов длиной 2k, из которых k являются нулями. Теперь, решив эту задачу с помощью алгоритма ESPP, мы получим две последовательности длины k, разница сумм которых минимальна. Поскольку нулевые элементы не меняют суммы, то мы можем "перегнать" их из одной последовательности в другую, соответственно, сводя задачу к PP.
Раз мы доказали, что задача NPC, то полиномиального алгоритма решения этой задачи не существует. Можете воспользоваться псевдополиномиальным алгоритмом из википедии, адаптировав его для себя или любым жадным алгоритмом из тех, что предложен ниже.
