Populate array with subarrays which have a max sum from flat array of numbers

Question

I need to fill an array which may contain an indeterminate number of subarrays (pallets) -- each with a maximum size of 265cm.

I have a flat array of integers (packs) which need to be optimally arranged in pallets (for example 50cm, 45cm, 30cm, ...).

How can I dynamically create a system that creates the multidimensional array that represents pallets with the best space optimization?

This is my code:

for ($i=0; $i < $mix_cc; $i++) { 
    foreach ($sh_array as $key => $row) { 
        $cm_remaining = $default_cc_height_fa - $sh_size;
        $sh_size = $sh_size + $row['size'];                   
        if ($row['size'] < $cm_remaining) {
            $mix_cc_array[$cc_number][$key] = $sh_array[$key];                   
        } else {
            $mix_cc_array[$cc_number + 1][$key] = $sh_array[$key];             
        }
        unset($sh_array[$key]);
    }
    $cc_number++;   
}

Answer 1

To optimize the space in the pallets, you can try the following First Fit Decreasing (FFD) approach:

Sort the array of packs by size in descending order. This way, you can start by adding the largest packs first and try to fit as many of them as possible in the pallet.

Iterate through the sorted array of packs and try to fit each pack in the current pallet. If the pack fits, add it to the pallet; If the pack does not fit, create a new pallet and add the pack to it.

Here's some sample code that demonstrates how you can implement this approach:

$default_cc_height_fa = 265; // size of the pallet in cm
$sh_array = [50, 45, 30, 60, 70, 80]; // array of packs

// sort the array of packs in decreasing order of size
usort($sh_array, function($a, $b) {
    return $b - $a;
});

// initialize the array of pallets
$mix_cc_array = [];

// iterate through the array of packs
foreach ($sh_array as $pack) {
    // try to fit the pack into an existing pallet
    $packed = false;
    foreach ($mix_cc_array as &$pallet) {
        if ($pack <= $default_cc_height_fa - array_sum($pallet)) {
            $pallet[] = $pack;
            $packed = true;
            break;
        }
    }
    // if the pack does not fit into any existing pallet, create a new one
    if (!$packed) {
        $mix_cc_array[] = [$pack];
    }
}

print_r($mix_cc_array);

Sandbox Example: https://onlinephp.io/c/45ca2

This should give you an array of pallets that are optimally packed in terms of space utilization using the First Fit Decreasing (FFD) method. You can also look into the Next Fit Decreasing (NFD) method if this one doesn't work for you.