12

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

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

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

12
  • А что делать, если у вас не могут быть равны части, как не дели? Можно перемещать элементы?
    – Dex
    1 июн 2012 в 20:33
  • входящий массив должен быть четным. Перемещать можно
    – ArniLand
    1 июн 2012 в 20:36
  • Вам нужен сам алгоритм или как это сделать на определенном языке?
    – Deonis
    1 июн 2012 в 20:38
  • мне нужно реализовать на C#
    – ArniLand
    1 июн 2012 в 20:41
  • 1
    @Merlin и то и другое)
    – misha_m
    2 июн 2012 в 18:10

7 ответов 7

13
  • Вы переформулировали так называемую 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, то полиномиального алгоритма решения этой задачи не существует. Можете воспользоваться псевдополиномиальным алгоритмом из википедии, адаптировав его для себя или любым жадным алгоритмом из тех, что предложен ниже.
6
  • 2
    Но ведь просят, чтобы A и B были равного размера. Этот алгоритм так не работает.
    – avp
    1 июн 2012 в 21:24
  • 1
    авп, не просят, я тоже считал вариант с равными половинками.. да и кстати, если разница не делится на 2, но массив не поделится на равные части..
    – Gorets
    1 июн 2012 в 21:27
  • 1
    @avp, я думаю, что ТС, говоря о равности, имел в виду не равные по размеру массивы, а всё же равные по сумме значений. Но тут бы неплохо, чтоб сам автор уточнил.
    – Deonis
    1 июн 2012 в 21:28
  • 1
    @Deonis почему-то я подумал тоже о равности и в размере массивов.
    – misha_m
    1 июн 2012 в 21:32
  • 2
    В заголовке вопроса написано две равные части, суммы элементов которых наиболее близки к равности
    – avp
    1 июн 2012 в 21:38
5

В продолжение к моим коментариям

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

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

сумма_массива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).'<br />'.array_sum($arr_second);

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

8
  • 2
    Что-то я тоже сомневаюсь) По-моему это задаче о рюкзаке, где стоимость каждого элемента 1, вес - элемент. А вместимость половина суммы массива. Как только находим решение стоимостью n/2 (где n - количество элементов в массиве) останавливаемся и восстанавливаем массив. Хотя может мне просто поспать надо (тоже не уверен) :)
    – misha_m
    1 июн 2012 в 21:18
  • Ну, если плюсуют вариант, который предложил @Котик_хочет_кушать, то всё-таки алгоритм выбран правильный, т.к. практически идентичный
    – Deonis
    1 июн 2012 в 21:24
  • Тоже (как и у @Котик) не то. Алгоритм не обеспечивает равного размера частей. В этом-то (одно из условий вопроса) и загвоздка.
    – avp
    1 июн 2012 в 21:28
  • @avp, Ответил выше ))
    – Deonis
    1 июн 2012 в 21:29
  • @Deonis Вы про Ваш алгоритм?
    – misha_m
    1 июн 2012 в 21:33
2

Как вариант можно предложить генетический алгоритм.

FitnessFunction понятно сумма (чем ближе к половине суммы всех элементов массива, тем круче)

Хромосома состоит из n/2 ген (ген - элемент массива).

Поиграться количеством популяции, посмотреть сколько примерно будет нужно для более менее адекватного результата. Ну и подумать как скрещивать (можно наверно сортировать гены в родителях и циклически скрещивать)

Опять же результат будет примерным (для улучшения можно несколько раз прогнать алгоритм и выбрать лучший результат)

4
  • @rasmisha - Извините, что стер свой прошлый коммент под моим ответом, просто размышлял над доказательством того, что это - NPC задача. - Не уверен, кстати, что ff, у которой метрика хорошести пропорциональна отклонению от полусуммы - это хороший выбор. Хотя не очень силен в генетических алгоритмах. 1 июн 2012 в 22:33
  • 1
    @Котик на счет ff вполне может быть. Просто решил поделиться вариантом, который пришел в голову и показался одним из способов найти приближенный ответ.
    – misha_m
    1 июн 2012 в 22:43
  • @Котик кстати, первая идея (не знаю насколько она правильна) как раз совпадает с вашей (по-крайней мере судя по ссылкам приведенным Вами), но не уверен опять же, что правильно распределил вес/стоимость/вместимость.
    – misha_m
    1 июн 2012 в 22:45
  • 1
    @rasmisha - Да, мне тоже, как только я глянул на вопрос, пришла в голову идея, что, собственно, две части массива - это два рюкзака c N / 2 элементов каждый. Но здесь не очень понятно, как строго установить ограничения для суммарного веса. А цена нестрогим заявлениям при работе с алгоритмами известна всем :) - Может быть, есть какие-нибудь другие формулировки Knapsack Problem, которые лучше подойдут для этого случая, не проверял. 1 июн 2012 в 22:54
2

Вроде работает :) Для массива с четным количеством элементов. Для нечетного чуть подправить надо, а лениво )

Суть такая. Сортируем изначальный массив. Заполняем оба выходных массива одновременно по одному числу в каждый. В массив с меньшей суммой добавляем бОльшее число, в массив в с бОльшей суммой добавляем элемент, при добавлении которого бОльший массив так и останется с бОльшей суммой (начинаем проверять с наименьшего элемента, если так и остался с большей, значит добавляется первый элемент и т.д.).

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

6
  • 1
    - Для [0,1,2,2,2,3,4,7,10,40,54,60,120,127] проявляется жадность алгоритма. - Ваш алгоритм вернет [127,54,10,7,4,3,2] и [120,60,40,0,1,2,2], но можно получить меньший разброс сумм, если, например, поменять 54 и 60 местами. - А вообще круто, что вам было не влом этим заниматься :) 1 июн 2012 в 23:05
  • В общем, некоторые способы будут в какой-то мере правильно работать, если разрядность чисел будет примерно одинакова, НО если одно число будет значительно больше, то все сойдёт на нет. Вот даже на вашем примере. ))) Так что, пора со спокойной душей ложиться спать ;)
    – Deonis
    1 июн 2012 в 23:10
  • @Deonis В примере со 100500 алгоритм как раз правильно отработал - он вернул результат с минимально возможной разницей, так что видимо со спокойной душой не получится :) 1 июн 2012 в 23:13
  • Хм, да ) Можно убавить жадность проверкой увеличения разлета для j==k-1. если разность сумм увеличивается при выборе максимальных элементов, то менять их местами. Вполне вероятно, что и этого недостаточно будет. Задачка интересная, да. 1 июн 2012 в 23:14
  • @Yura Ivanov неужели Вы из-за этого не спали?
    – misha_m
    2 июн 2012 в 0:52
0
  1. смотрим на длину массива
  2. смотрим на суммы половинок
  3. если равные - профит
  4. если нет, смотрим разницу и запоминаем
  5. разницу делим на 2
  6. ищем это значение (разницу/2) в части, где больше
  7. делим ее(разницу/4) еще на 2 и ищем это значение(то что получилось) в левой части
  8. меняем их(то что нашли в половинках массива) местами

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

9
  • Я думаю, что пункты 1-4 надо немного видоизменить на поиск границы в массиве, на которой разность суммы элементов частей меняет свой знак или равны.
    – Dex
    1 июн 2012 в 20:54
  • раз 5 прочитал. Не понял пункты 6-8 )
    – misha_m
    1 июн 2012 в 20:55
  • 1
    @Gorets, тут скорее возникает вопрос, что делать если: 1. Разница не делится на 2 нацело 2. в большей части нет этого значения 3. что делать если (7) не делится на 2 нацело 3. в меньшей части нету этого значения
    – Dex
    1 июн 2012 в 20:59
  • @Dex, возможно, но пока что мне кажется твой алгоритм сложнее @rasmisha, дополнил
    – Gorets
    1 июн 2012 в 21:02
  • 3
    Неплохая попытка наскоком придумать алгоритм для NPC задачи :) 1 июн 2012 в 21:13
0

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

-2
  1. Отсортировать массив.
  2. Брать суммы значений крайних элементов массива и складывать их поочередно в одну из двух переменных.
  3. Если длинна массива нечётная - прибавить к меньшей из двух переменных значение центрального элемента.
5
  • 1
    Жадный алгоритм как было уже сказано даст примерный результат.
    – misha_m
    1 июн 2012 в 21:58
  • Т. е. я его просто расписал на словах? 1 июн 2012 в 22:00
  • Ну что-то похожее по крайней мере
    – misha_m
    1 июн 2012 в 22:07
  • оформление ответа слизано с ответов тов. @Котик_хочет_кушать
    – Spectre
    2 июн 2012 в 7:05
  • 1
    > Если моё решение не правильное - не минусуйте XD Я в домике! :-D Логичное возражение: А я - мистер Нейтрон!
    – karmadro4
    2 июн 2012 в 9:58

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.