PHP - Organize objects into arrays based on property value until condition is met

Question

I am trying to figure out how to code the following

• Array of objects, each object has a property for weight
• Loop over the objects and sort them into new arrays, each array containing as much as possible but not exceeding X lbs.

A simple loop to add items and when the total weight of the current array is >= X lbs, create a new array and continue, that part is easy. However I want the final result to be as efficient as possible meaning that each array contains the most possible items without exceeding the max.

I apologize if I'm not explaining this correctly, but does anyone know what I mean here? I think the root of what I'm trying to do is sort these items using mathematical optimization.

Thank you!

Answer 1

There are many solutions for this, as explained in Sammitch's link.

Here is a basic one that likely isn't going to give the best result, nor be the fastest, but should be a good start. The key part is sorting them by weight at the start. Then it just loops through them, testing if they'll fit in the current container, as you said. It gave reasonable results for me.

Demo link: https://3v4l.org/KWrZo

<?php

$max_weight = 100;

// init with some random weights
$objects = [];
for ($i = 1; $i <= 100; $i++) {
    $objects[] = (object) ['id' => $i, 'weight' => rand(1, 50)];
}

// sort by weight, heaviest first
usort($objects, function ($a, $b) {
    return $b->weight <=> $a->weight;
});

$containers = [];
$container_number = 0;
$total_weight = 0;

while (true) {

    $container_number++;

    $container = [];
    $container_weight = 0;

    foreach ($objects as $key => $object) {
        // add this object to the container if it won't push it over the max weight
        if ($container_weight + $object->weight <= $max_weight) {
            $container[] = $object;
            unset($objects[$key]);
            $container_weight += $object->weight;
            $total_weight += $object->weight;
            if ($container_weight == $max_weight) {
                break;
            }
        }
    }

    $containers[$container_number] = $container;
    $container_contents = count($container);

    echo 'Container #' . $container_number . ' total weight: ' . $container_weight . ' (' . $container_contents . ' items)' . PHP_EOL;

    if (empty($objects)) {
        break;
    }
}

echo 'Total weight: ' . $total_weight . PHP_EOL;

var_dump($containers);