用具有平面数字数组的最大和的子数组填充数组

Question

我需要填充一个数组，该数组可能包含不确定数量的子数组(托盘)-每个子数组的最大尺寸为265cm。

我有一个整数(包)的平面数组，需要在托盘中进行最佳排列(例如50cm, 45cm, 30cm，…)。

我如何动态创建一个系统，创建多维数组，代表托盘与最佳空间优化?

这是我的代码:

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

要优化托盘中的空间，您可以尝试以下第一次缩小(FFD)方法:

按大小降序对包数组进行排序。这样，您可以先添加最大的包装，并尝试在托盘中尽可能多地安装它们。

遍历已排序的包数组，并尝试在当前托盘中匹配每个包。如果包装合适，将其添加到托盘;如果包装不适合，创建一个新的托盘，并将包装添加到其中。

下面是一些示例代码，演示如何实现这种方法:

$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);

沙盒示例:https://onlinephp.io/c/45ca2

这将为您提供一个托盘数组，这些托盘使用第一次匹配减少(FFD)方法在空间利用率方面进行了最佳包装。如果这个方法不适合你，你也可以看看下一个匹配减少(NFD)方法。

Answer 2

这里有两个简洁的代码片段来实现First Fit递减和Next Fit递减算法。我怀疑您会倾向于FFD算法，因为它试图在打开一个新的托盘之前完全包装早期的托盘。我的理解是，NDD是为性能而优化的，但FFD是为最小托盘而优化的。

_{如果我对这些算法的理解不完全准确，我很高兴被纠正。}

代码(演示):

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

和

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