Разделение массива по равенству двух частей

#алгоритм

Как разделить массив на две равные части, суммы элементов которых наиболее близки
к равенству.
Как разделить массив по на две части, я знаю. Но не могу придумать, как сделать?
чтобы суммы элементов этих двух частей были равны. Прошу подсказать алгоритм.
Для тех, кто просил уточнить условие: массив делится на две равные части, количество
элементов первой части = количеству элементов второй. Также сумма элементов первой
части равна или наиболее близка к равенству второй части.    

Ответы

Ответ 1

Вы переформулировали так называемую 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, то полиномиального алгоритма решения этой задачи
не существует. Можете воспользоваться псевдополиномиальным алгоритмом из википедии,
адаптировав его для себя или любым жадным алгоритмом из тех, что предложен ниже.


Ответ 2

В продолжение к моим коментариям
В заголовке темы, вы указываете, что если не абсолютно равны, то максимально приближены
к равенству. Тогда, на PHP я сделал следующим образом:

Посчитал сумму значений массива и разделил её на два
Отсортировал массив по убыванию значений
Перебираем отсортированный масси


сумма_массива1 = 0;
сумма_массива2 = 0;
если (суммамассива1 <= суммамассива2 || суммамассива2 >= полобщей_суммы){
добавить значение в массив1

сумма_массива1 += значение;

} вдругомслучае {
добавить значение в массив2

сумма_массива2 += значение;

}

Код на PHP (проверить можно его тут - http://writecodeonline.com/php/):
$arr = array(10,68,30,28,34,74,52,20,176,18,86,14,22,4); // исходный массив
rsort($arr,SORT_NUMERIC); // сортируем по значениям в обратном порядке
$halfSum = intval(array_sum($arr) / 2); // высчитываем сумму значений и делим на
две примерно равные части

$arr_first = array(); // первый массив
$arr_second = array(); // второй массив
$sum1 = 0; // сумма первого массива для сравнения
$sum2 = 0; // сумма второго массива для сравнения
// перебираем отсортированный исходный массив
foreach($arr as $val){
    // сумма первого массива меньше второго 
    // и сумма второго массива больше или равна половине общей суммы
    // то очередное значение добавляется в первый массив
    // в ином случае - во второй массив
    if($sum1 <= $sum2 || $sum2 >= $halfSum){
        $arr_first[] = $val;
        $sum1 += $val;
    } else {
        $arr_second[] = $val;
        $sum2 += $val;
    }
}
//выводим суммы обоих массивов
echo array_sum($arr_first).'
'.array_sum($arr_second);

Конечно далеко не уверен, что работает корректно, но несколько раз протестил и вроде
бы как все нормально сделало.


Ответ 3

Как вариант можно предложить генетический алгоритм.
FitnessFunction понятно сумма (чем ближе к половине суммы всех элементов массива,
тем круче)
Хромосома состоит из n/2 ген (ген - элемент массива).
Поиграться количеством популяции, посмотреть сколько примерно будет нужно для более
менее адекватного результата. Ну и подумать как скрещивать (можно наверно сортировать
гены в родителях и циклически скрещивать)
Опять же результат будет примерным (для улучшения можно несколько раз прогнать алгоритм
и выбрать лучший результат)


Ответ 4

Вроде работает :) Для массива с четным количеством элементов. Для нечетного чуть
подправить надо, а лениво )
Суть такая. Сортируем изначальный массив. Заполняем оба выходных массива одновременно
по одному числу в каждый. В массив с меньшей суммой добавляем бОльшее число, в массив
в с бОльшей суммой добавляем элемент, при добавлении которого бОльший массив так и
останется с бОльшей суммой (начинаем проверять с наименьшего элемента, если так и остался
с большей, значит добавляется первый элемент и т.д.).
UPD Проблема жадности проявляется на этапе когда выбираются максимальные элементы.
Когда выбирается максимальный и один из минимальных элементов, жадность не влияет на
выбор. Соответственно эту неопределенность предлагаю ветвить. Находим все множества
решений исходя и того, что максимальные элементы могут принадлежать как первому-второму
массиву, так и второму-первому. А затем выбираем наиболее подходящее с точки зрения
минимальности разности сумм. В худшем случае будет брутфорс, жаль.


Ответ 5

смотрим на длину массива
смотрим на суммы половинок
если равные - профит
если нет, смотрим разницу и запоминаем 
разницу делим на 2
ищем это значение (разницу/2) в части, где больше
делим ее(разницу/4) еще на 2 и ищем это значение(то что получилось) в левой части
меняем их(то что нашли в половинках массива) местами

алгоритм прикинул на глаз, мб неправильно, проверьте, поправьте и если не правильно,
простите


Ответ 6

Можно запустить бинарный поиск по ответу, а для каждого значение проверять алгоритмом
для набора рюкзака, можем ли мы набрать рюкзак данного размера. Сложность O(N ** N
logN). Если ответ есть, он находится, можно и доработать для поиска двух подмассивов
минимальной разности. Это как вариант.


Ответ 7

Отсортировать массив.
Брать суммы значений крайних элементов массива и складывать их
 поочередно в одну из двух переменных.
Если длинна массива нечётная - прибавить к меньшей из двух переменных значение
 центрального элемента.