Question 41116 in PHP Question posted in
Official manual can be found here.

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

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

2

Answers


  1. 0

    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.

    Login or Signup to reply.
  2. 0

    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;
}
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search