合并两个数组以使整数值尽可能接近相等

Question

申请在仓库之间分配库存

我有两个数组，

一个有仓库列表以及当前数量：（这可以是一个或多个位置的动态）

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

Other 数组具有即将进入的库存量：

[
     'qty' => 5
]

并且想要在各个位置之间分配数量，以便每个位置的当前数量彼此接近相等。所以想要 return 一个数组，其中包含需要添加到每个位置的数字。喜欢：这里，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 是要划分的耗材数量）。我会把那个实现留给你。

提示：有a look at recursive functions

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

合并两个数组以使整数值尽可能接近相等

Merge Two Arrays to Have an Integer Value be an near equal as possible

php

sorting

algorithm

math

distribution