Не так давно мне на глаза попалась очень интересная задачка, которую нужно было решить на PHP. С первого взгляда она мне показалась не очень сложной, но впоследствии на ее решение и изучение всего необходимого материала у меня ушло достаточно большое количество времени. Все дело в том, что задача была связана с очень распространённой в динамическом программировании так называемой «Partition problem»…
Итак, ниже привожу текст самой задачи:
Есть массив цифр. Необходимо создать функцию, которая разбивает этот набор на N групп так, чтобы сумма цифр в каждой группе была максимально равной.
Т.е к примеру если у нас есть массив чисел 1,2,4,7,1,6,2,8 и его нужно разбить на 3 группы, то на выходе должно получиться: (8,2) | (7,2,1) | (6,4,1).
Многие из вас подумают, что для решения этой задачи хватит использования array_chunk()
, но вся суть кроется именно в словах — «сумма цифр в каждой группе была максимально равной». Кстати во время жесточайшего «гуглинья» хоть каких-то намеков на решения данной задачи я находил кучу готовых решений в одну строку с использованием array_chunk()
, но все они естественно были неправильные т.к. просто «били» массив на части. В конечном итоге я натыкаюсь на видео на youtube в котором очень хорошо описывается решение задачи, но только при условии что массив разбивается на две части.
После просмотра видео, я нахожу очень интересную статью из википедии полностью посвященную «Partition problem» в которой как раз описаны все алгоритмы решения моей задачи.
Дальше решение не заставило себя ждать, и в итоге у меня получился вот такой код:
<?php $big_array = array(1,2,4,7,1,6,2,8); $big_group = 3; function fun_partition($array, $part) { $part = round($part); $array_len = count($array); if($part <= 0 || $array_len < $part) { return $array; } else { $out = array_fill(0, $part, array()); rsort($array, SORT_NUMERIC); foreach($array as $value) { usort($out, function($a, $b){ return array_sum($a) > array_sum($b); }); $out[0][] = $value; } return $out; } } ?> <pre> <?php print_r(fun_partition($big_array, $big_group)); ?> </pre>
На выходе получаем требуемое верное разбиение массива с помощью «жадного алгоритма».
На этом все, надеюсь мой вариант решения поможет кому-нибудь в дальнейшем. В завершении статьи хочу посоветовать вам почитать дополнительно вот это.