0

Всем привет. За основу взят алгоритм O(n log n) https://en.wikipedia.org/wiki/Partition_problem Только проблема в том, что конструкция не жизнеспособна в случае если на вход может приходить разное кол-во колонок

<?php

function partList($arr, $groups) {

$a = [];
$b = [];
$c = [];

$arrCount = count($arr);
$result = [];

sort($arr, SORT_NUMERIC);

for ($i = 0; $i < $arrCount; $i++) {
    if (array_sum($a) < array_sum($b)) {
        $a[] = $arr[$i];
    } else if (array_sum($b) < array_sum($c)){
        $b[] = $arr[$i];
    } else {
        $c[] = $arr[$i];
    }
}


var_dump($a, $b, $c);
}


$arr = [1,2,4,7,1,6,2,8];

partList($arr, 3);

Т.е. не понимаю что дальше делать с groups, как должен выглядеть встроенный в for еще один цикл который примет кол-во груп и разобьет на них чтобы не приходилось каждый раз расписывать условия?

http://sandbox.onlinephpfunctions.com/code/a823a059aa787339dd823cc1b3e23b9879b2b99a

6
  • он разобьет массив на равные части, а по алгоритму нужно чтобы цифры группировались по схожим суммам примерно Commented 30 мая 2018 в 11:03
  • Чего? array_chunk - возвращает массив, разделенный на равные части, последний массив из полученных может содержать меньшее количество значений, чем указано в size. Иначе просто невозможно сделать.
    – And
    Commented 30 мая 2018 в 11:07
  • 1
    в вашей ссылке приведен не алгоритм, а сама задача, и несколько вариантов ее решения. в конце статьи сказано. что для N-групп следует изучать другую задачу
    – teran
    Commented 30 мая 2018 в 11:08
  • @And по сумме надо разбить, а не по числу элментов. Чтобы сумма чисел в каждой части была примерно одинакова. минимизироватьразницу этих сумм. задача оптимизации.
    – teran
    Commented 30 мая 2018 в 11:09
  • @teran, а, то есть ему нужно разбирать указанное количество элементов, допустим 3, и каждые 3 суммировать так, чтобы они были похожи с следующим, а последний получается не важно ибо элементов может быть меньше или другая сумма?
    – And
    Commented 30 мая 2018 в 11:13

1 ответ 1

1

Как-то так:

function partList($arr, $groups = 3){
    $newArray = array_fill(0, $groups, []);
    rsort($arr, SORT_NUMERIC);
    foreach ($arr as $value){
        usort($newArray, function($one, $thwo){
            return array_sum($one) > array_sum($thwo);
        });
        $newArray[0][] = $value;     
    }
    return $newArray;
}
$arr = [1,2,4,7,1,6,2,8];
print_r(partList($arr));

Вывод:

Array
(
    [0] => Array
        (
            [0] => 7
            [1] => 2
            [2] => 1
            [3] => 1
        )

    [1] => Array
        (
            [0] => 8
            [1] => 2
        )

    [2] => Array
        (
            [0] => 6
            [1] => 4
        )

)

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

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

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