Решение 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» в которой как раз описаны все алгоритмы решения моей задачи.

Дальше решение не заставило себя ждать, и в итоге у меня получился вот такой код:

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

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

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