Решение partition problem на PHP

Не так давно мне на глаза попалась очень интересная задачка, которую нужно было решить на 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>

На выходе получаем требуемое верное разбиение массива с помощью «жадного алгоритма».

На этом все, надеюсь мой вариант решения поможет кому-нибудь в дальнейшем. В завершении статьи хочу посоветовать вам почитать дополнительно вот это.

Подписаться на новые статьи