2

I wanted to get the sum of values and limit them with a maximum value. My maximum value is 500.

My array:

array:11 [
  0 => 100
  1 => 100
  2 => 100
  3 => 100
  4 => 100
  5 => 100
  6 => 300
  7 => 300
  8 => 300
  9 => 300
  10 => 300
  11 => 300
  12 => 300
  13 => 300
  14 => 300
  15 => 300
]

So each 100 will be sum up to 500 and end up getting this array below.

Desired output:

array:11 [
  0 => 300
  1 => 300
  2 => 300
  3 => 300
  4 => 300
  5 => 300
  6 => 300
  7 => 500
  8 => 500
  9 => 500
]

This is what I did so far. Tried to sort all numbers from lowest to highest using usort.

usort($orderSumArr, function ($a, $b) {
   return $a > $b;
});

$sumArr = [];
$current = 0;
foreach ($sumArr as $num) {
   if ($current + $num <= 500) { // limit up to 500
       $current += $num;
   } else {
       $sumArr[] = $current;
       $current = $num;
   }
}

$sumArr[] = $currentSum2;

And this is the output I'm getting. It ends up adding the first 100 which produce 500 and the remaining 100 was added to 300 which sum up to 400.

array:11 [
  0 => 300
  1 => 300
  2 => 300
  3 => 300
  4 => 300
  5 => 300
  6 => 300
  7 => 300
  8 => 300
  9 => 400
  10 => 500
]
mickmackusa
  • 43,625
  • 12
  • 83
  • 136
the_lorem_ipsum_guy
  • 452
  • 1
  • 12
  • 27
  • This looks like a "bin packing" problem, which is best solved using dynamic programming. – Barmar Aug 12 '21 at 17:00
  • 1
    Sort the array from highest to lowest. Get a value from the array, then go through the rest of the array looking for values that you can add while staying under the limit. Remove them from the array as you find them. Keep repeating this until you hit the limit or can't find anything to add. Then do this again for the next element of the array. – Barmar Aug 12 '21 at 17:02
  • Removing from an array while you're iterating over it is complicated, though. – Barmar Aug 12 '21 at 17:02
  • @Barmar it's kinda complicated what you mentioned here but I've got an idea. If you don't mind, can you post how you've done it? – the_lorem_ipsum_guy Aug 12 '21 at 17:10
  • I haven't done it. Like I said, it's complicated.... – Barmar Aug 12 '21 at 17:16
  • @Barmar no worries man. your comment is already helpful. I will try to implement it. thanks a lot!! – the_lorem_ipsum_guy Aug 12 '21 at 17:33
  • Why is your current output incorrect/unsuitable? Do you need minimal buckets? Can the input elements not be distributed to multiple other elements? – mickmackusa May 28 '23 at 12:31
  • [Algorithm to find best combination of numbers - Bin Packing Problem](https://stackoverflow.com/q/41463561/2943403) – mickmackusa May 28 '23 at 12:50

1 Answers1

0

There are multiple theoretical solutions to the "Bin Packing Problem". Some are optimized for computational efficiency at a cost of result accuracy. The most reliable algorithms are very demanding on resources. One less expensive approach is the "First Fit Decreasing" strategy. Your desired output is simpler than the classic task, because you expect the consolidated sums rather than keeping each item separate per bin.

Code: (Demo)

function consolidate(array $array, int $capacity = 500): array
{
    rsort($array);
  
    $bins = [0];
    foreach ($array as $value) {
        foreach ($bins as &$bin) {
            if ($capacity >= $bin + $value) {
                $bin += $value;
                continue 2;
            }
        }
        $bins[] = $value;
    }
  
    return array_values(array_filter($bins));
}

var_export(consolidate($array));

For best results and if you have the available resources, generate an exhaustive list of all possible combinations and choose the one with the fewest elements.

mickmackusa
  • 43,625
  • 12
  • 83
  • 136