Объединение двух массивов, чтобы иметь целочисленное значение, равное максимально возможному

Question

Приложение для распределения запасов между складами

У меня есть два массива,

У одного есть список складов вместе с текущим количеством: (Это может быть динамический с одним(или более местоположений)

[
    ['location_name' => 'Toronto',    'current_qty'   => 3],
    ['location_name' => 'Mississauga','current_qty'   => 7],
    ['location_name' => 'London',     'current_qty'   => 5],
]

В массиве Other есть сумма запаса, которая будет поступать в:

[
     'qty' => 5
]

и необходимо распределить кол-во между местоположениями, чтобы текущий кол-вокаждого из местоположений будет почти равным друг другу.Так что хотите вернуть массив с номером, который нужно добавить в каждое место.Как: Здесь из 5, 3 отправились в Торонто, а 2 в Лондон .Таким образом, это видно, что после ближайшего выравнивания остаток распределения может быть сделан случайным образом.

[
    ['location_name' => 'Toronto',    'add_qty'   => 3],
    ['location_name' => 'Mississauga','add_qty'   => 0],
    ['location_name' => 'London',     'add_qty'   => 2],
]

И просто не могу понять логику этого алгоритма.Был бы очень признателен за любые указатели.Большое спасибо.

Answer 1

Я бы сделал это так, не будучи уверенным в каких-либо проблемах с производительностью. Я не знаю, насколько велик ваш набор данных.

$locations = [
    ['location_name' => 'Toronto', 'current_qty' => 3, 'add_qty' => 0],
    ['location_name' => 'Mississauga', 'current_qty' => 7, 'add_qty' => 0],
    ['location_name' => 'London', 'current_qty' => 5, 'add_qty' => 0],
];

$supplies = 5;

// This function sorts locations, by comparing the sum of the current quantity and the quantity the location will get.
$locationsByQuantityAscending = function ($locationA, $locationB) {
    return ($locationA['current_qty'] + $locationA['add_qty']) - ($locationB['current_qty'] + $locationB['add_qty']);
};

// Sort the locations, getting the ones with the lowest quantity first.
usort($locations, $locationsByQuantityAscending);

// Keep dividing, until we're out of supplies
while ($supplies > 0) {
    $locations[0]['add_qty']++; // Add one to the location with the lowest supplies
    $supplies--; // Decrease the supplies by one
    usort($locations, $locationsByQuantityAscending); // Sort the locations again.
}

print_r($locations);

В конце вы получите:

Array
(
    [0] => Array
        (
            [location_name] => Toronto
            [current_qty] => 3
            [add_qty] => 3
        )

    [1] => Array
        (
            [location_name] => London
            [current_qty] => 5
            [add_qty] => 2
        )

    [2] => Array
        (
            [location_name] => Mississauga
            [current_qty] => 7
            [add_qty] => 0
        )

)

Если вам действительно нужно быть эффективным, вы также можете просто отсортировать места по их текущему количеству. Затем продолжайте добавлять к первому местоположению, пока его запас не будет выше, чем второе местоположение. Затем, пока количество во втором местоположении не станет больше, чем в третьем местоположении, добавьте единицу в первое и второе местоположение и т. Д.

Я думаю, что это будет более производительным, так как вам не нужно сортировать все ваши местоположения X раз (X - количество расходных материалов, которое нужно разделить). Я оставлю эту реализацию вам.

Подсказка: посмотрите на рекурсивные функции

Answer 2

Если производительность критична, а входные данные обычно больше, чем показано здесь (например, намного больше мест или намного больше для распространения).Возможно, вы захотите использовать SplMinHeap:

Например:

<?php

$helper = new class extends SplMinHeap
{
    public function compare($a, $b): int
    {
        return ($b['current_qty'] + $b['add_qty']) <=> ($a['current_qty'] + $a['add_qty']);
    }
};

$locations = [
    ['location_name' => 'Toronto',     'current_qty' => 3, 'add_qty' => 0],
    ['location_name' => 'Mississauga', 'current_qty' => 7, 'add_qty' => 0],
    ['location_name' => 'London',      'current_qty' => 5, 'add_qty' => 0],
];

foreach ($locations as $entry) {
    $helper->insert($entry);
}

$qty = 10000;
while ($qty-- > 0) {
    $min = $helper->extract();
    $min['add_qty']++;

    $helper->insert($min);
}

print_r(iterator_to_array($helper));

https://3v4l.org/nDOY8