php - Distribute total amount to a flat array of "container" elements with predefined limits - Stack Overflow

admin管理员组

文章数量:1122846

I'm trying to split items evenly through groups with a max on each group.

I have a function which receives a $groups array which declares the maximum capacity of each "group" and an $items integer which declares the total value which can be distributed across the elements of $groups.

This is my function so far:

public static function splitItems($groups, $items) {
    $n = count($groups);
    $res = array_fill(0, $n, 0);

    while ($items >= $groups[0]) {
        for ($i = $n - 1; $i >= 0; $i--) {
            if ($items >= $groups[$i]) {
                $res[$i]++;
                $items -= $groups[$i];
            }
        }
    }

    if ($items > 0) {
        $res[0]++;
    }
    return $res;
}

My function isn't properly taking into account the VALUE of array as max value. What I'm looking for are this results:

Input:

splitItems([14, 2], 10);
splitItems([6, 8, 2], 14);

Output:

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

I'm trying to split items evenly through groups with a max on each group.

I have a function which receives a $groups array which declares the maximum capacity of each "group" and an $items integer which declares the total value which can be distributed across the elements of $groups.

This is my function so far:

public static function splitItems($groups, $items) {
    $n = count($groups);
    $res = array_fill(0, $n, 0);

    while ($items >= $groups[0]) {
        for ($i = $n - 1; $i >= 0; $i--) {
            if ($items >= $groups[$i]) {
                $res[$i]++;
                $items -= $groups[$i];
            }
        }
    }

    if ($items > 0) {
        $res[0]++;
    }
    return $res;
}

My function isn't properly taking into account the VALUE of array as max value. What I'm looking for are this results:

Input:

splitItems([14, 2], 10);
splitItems([6, 8, 2], 14);

Output:

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

• php
• arrays
• distribution

Share Improve this question Follow edited Nov 25, 2024 at 20:50 mickmackusa 47.7k1313 gold badges9292 silver badges159159 bronze badges Recognized by PHP Collective asked Nov 22, 2024 at 14:02 EredEred 49711 gold badge66 silver badges2424 bronze badges 5

• 1 the array keys are the max value for each group...it's unclear what this means in relation to the sample data supplied. In your example ([14,2],10) the array keys of the supplied array will be 0 and 1. But the values in your output groups are 8 and 2. Did you mean to say the array values (i.e. 14 and 2 in that example)? Make sure you get the terminology right, otherwise the question can be come ambiguous or confusing. – ADyson Commented Nov 22, 2024 at 14:11
• 1 @ADyson I meant the array VALUES of the supplied array will be 14 and 2 sorry, also I added another example, please let me know if thats good or u need more examples on Input and output – Ered Commented Nov 22, 2024 at 14:20
• 1 I find this question to be VERY confusing. Mostly because of splitItems([1,1],10); the result is correct. But also, is the rule meant to be that the smallest capacities get satisfied first? Are the distributions generally meant to be balanced-ish? Is it intended that the largest capacity been given the fewest items when there are insufficient items? Do we have enough challenging test cases to fully interpret and test the requirements? – mickmackusa Commented Nov 23, 2024 at 0:12
• 1 @mickmackusa "is the rule meant to be that the smallest capacities get satisfied first? Are the distributions generally meant to be balanced-ish? Is it intended that the largest capacity been given the fewest items when there are insufficient items?" ...maybe the OP doesn't mind how the algorithm approaches these things, perhaps they're unimportant for the purpose they have in mind, and so they didn't specify them. The OP apparently doesn't think they're essential to solving the problem and it's possible to write code without involving those factors, so they should not be a barrier – ADyson Commented Nov 25, 2024 at 14:20
• 1 @mickmackusa thanks for taking time on reviewing my question, ADyson is correct I really dont mind how the algorithm approaches these things, however what I totatly miss was a condition when not enough space for all the items, which ADyson helped me out with. sorry for errors made at my initial post – Ered Commented Nov 25, 2024 at 14:32

Add a comment  | 

2 Answers 2

Sorted by: Reset to default 2

• To target smaller limits first, call asort() to order your elements ascending and preserve the original indexes.
• Then loop over the elements and update their value to be the lesser amount of their original value and the amount remaining in the total.
• Then reduce the total by the amount applied to the element and repeat.
• Before returning the updated elements, return them to their original order, if it matters.

This effectively fills the smaller capacities before larger capacities and never overfills. Demo

function splitItems(array $limits, int $total): array {
    asort($limits);
    foreach ($limits as &$limit) {
        $limit = min($limit, $total);
        $total -= $limit;
    }
    ksort($limits);
    return $limits;
}
    
var_export(splitItems([14, 2], 10));
echo "\n---\n";
var_export(splitItems([6, 8, 2], 14));
echo "\n---\n";
var_export(splitItems([6, 4, 2], 14));
echo "\n---\n";
var_export(splitItems([7, 7, 1], 4));
echo "\n---\n";
var_export(splitItems([1, 1], 10));
echo "\n---\n";
var_export(splitItems([2,1,3],4));

Output:

array (
  0 => 8,
  1 => 2,
)
---
array (
  0 => 6,
  1 => 6,
  2 => 2,
)
---
array (
  0 => 6,
  1 => 4,
  2 => 2,
)
---
array (
  0 => 3,
  1 => 0,
  2 => 1,
)
---
array (
  0 => 1,
  1 => 1,
)
---
array (
  0 => 2,
  1 => 1,
  2 => 1,
)

p.s. If you don't care about filling the smallest capacity first, or if filling the items in order of their initial position is desired, just remove the two *sort() calls.

---

Update: For balanced distribution, you can loop over the containers one-at-a-time until they are full or the total is entirely consumed. Demo

function splitItems(array $limits, int $total): array {
    $i = 0;
    $count = count($limits);
    $result = array_fill(0, $count, 0); // set 0 defaults for all containers
    do {
        if ($result[$i] < $limits[$i]) {  // this container still has room
            ++$result[$i];  // add 1 to container
            --$total; // subtract 1 from total          
        }
        $i = ($i + 1) % $count; // update $i with circular access to allow restarting from 0
    } while ($total && $result !== $limits);  // loop until $total is emptied or all limits are filled
    return $result;
}

This should work:

function splitItems($groups, $items)
{
    $n = count($groups);
    $res = array_fill(0, $n, 0);
    $groupsFilled = array_fill(0, $n, 0);;

    while ($items > 0 && count(array_keys($groupsFilled, 1)) < count($groupsFilled))
    {
        for ($i = $n-1; $i >= 0; $i--)
        {
            if ($res[$i] < $groups[$i])
            {
                if ($items > 0) {
                    $res[$i]++;
                    $items--;
                }
            }
            else $groupsFilled[$i] = 1;
        }
    }

    return $res;
}

print_r(splitItems([14,2],10));
print_r(splitItems([6,8,2],14));
print_r(splitItems([6,4,2],14)); //not enough space for all the items!

Outputs:

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

Key points:

• The code loops until there are no more items left to distribute (in most cases, but see the last bullet point below).
• As per your original logic it will put an item the last group first, and then work backwards to the first one. It distributes one item to each group, then goes round again until there's nothing left.
• It checks to ensure the group is not full before putting an item into it.
• If you specify less total space in the groups than there are items, it will just fill the groups until there is no space left in any of them - that's what the second condition in the while loop is doing. (What it doesn't do is tell you how many items couldn't be put into a group - but you could alter that if you wanted to.)

Live demo: https://3v4l.org/R8BOg

本文标签：