CODEWITHSUNDEEP
phparraysoptimizationmultidimensional-arrayfill
Sabino Sibillano
Sabino Sibillano

Reputation: 13

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

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++;   
}

Upvotes: 0

Views: 128

Answers (2)

mickmackusa
mickmackusa

Reputation: 47934

Here are two succinct snippets to implement the First Fit Decreasing and Next Fit Decreasing algorithms. I suspect you will lean toward the FFD algorithm because it attempts to fully pack early pallets before bothering to open a new one. My understanding is that NDD is optimized for performance, but FFD is optimized for minimal pallets.

If my understanding of these algorithms is not entirely accurate, I am happy to be corrected.

Codes: (Demo)

function nextFitDecreasing(array $items, int $max): array
{
    rsort($items);
    $result = [];
    foreach ($items as $item) {
        if (!isset($pallet) || (array_sum($pallet) + $item) > $max) {
            unset($pallet);
            $result[] = &$pallet;
        }
        $pallet[] = $item;
    }
    return $result;
}

And

function firstFitDecreasing(array $items, int $max): array
{
    rsort($items);
    $result = [];
    foreach ($items as $item) {
        foreach ($result as &$pallet) {
            if (array_sum($pallet) + $item <= $max) {
                $pallet[] = $item;
                continue 2;
            }
        }
        $result[] = [$item];
    }
    return $result;
}

Upvotes: 0

Crimin4L
Crimin4L

Reputation: 615

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.

Upvotes: 1

Related Questions