PHP数组按字符串长度接近指定阈值$limit分组并按总长度排序的实现咨询

我来帮你解决这个PHP数组分组的问题——要实现按元素长度之和尽可能接近指定阈值的最优分组，确实不能用简单的顺序累加，得用更合理的策略。先把需求和现有问题理清楚，再给出完整的解决方案。

需求说明 #

你的核心需求是：

• 将给定的PHP数组，按照**元素字符串长度之和尽可能接近指定阈值$limit**的规则分组
• 分组完成后，按每组的总长度从高到低排序
• 最终将每组元素用*连接成字符串

以$limit=29为例，输入数组：

$arr = [
    'Isofix',
    'Parkinghelp',
    'Rainsensor',
    'Led light',
    'Hill Start Assist',
    'Dynamic brake light',
    'Cornering Brake Control'
];

期望的最优分组组合（按总长度排序）：

• Cornering Brake Control（长度23） + Isofix（长度6）= 总长度29
• Dynamic brake light（长度19） + Rainsensor（长度10）= 总长度29
• Hill Start Assist（长度17） + Parkinghelp（长度11）= 总长度28
• Led light（长度9）单独成组

最终输出格式：

Array (
    [0] => Cornering Brake Control * Isofix
    [1] => Dynamic brake light * Rainsensor
    [2] => Hill Start Assist * Parkinghelp
    [3] => Led light
)

现有代码的问题 #

你当前的实现只是简单按数组顺序累加元素，一旦当前组加不下就新建组，这种方式完全没有考虑元素组合的可能性，自然无法找到最优解。比如它会先把Isofix加入第一个组，之后遇到长元素Cornering Brake Control时就只能单独成组，浪费了和Isofix组合凑到刚好29的机会。

贴出你的现有代码方便对比：

// 代码
$limit = 29;
$arr = array('Isofix', 'Parkinghelp', 'Rainsensor', 'Led light', 'Hill Start Assist', 'Dynamic brake light', 'Cornering Brake Control');
foreach ($arr as $key => $value) {
    echo $value . ' - ' . strlen($value);
    echo "\n";
}
// 当前实现（无法遍历所有组合）
$limit = 29;
$result9009 = array('');
$cur_key = 0;
foreach ($arr as $word) {
    if (strlen($result9009[$cur_key]) + strlen($word) <= $limit) {
        $result9009[$cur_key] .= ' * ' . $word;
    } else {
        $result9009[] = $word;
        $cur_key++;
    }
}

解决方案：贪心算法实现最优分组 #

这里我们采用贪心算法来实现，核心思路是：先处理最长的元素，再为每个元素找到能容纳它且加入后总长度最接近阈值的分组，这样能最大化利用阈值空间，得到最优的分组结果。

完整实现代码：

<?php
$limit = 29;
$arr = [
    'Isofix',
    'Parkinghelp',
    'Rainsensor',
    'Led light',
    'Hill Start Assist',
    'Dynamic brake light',
    'Cornering Brake Control'
];

// 1. 为每个元素绑定其字符串长度，方便后续计算
$items = array_map(function($item) {
    return [
        'value' => $item,
        'length' => strlen($item)
    ];
}, $arr);

// 2. 按元素长度从大到小排序——贪心策略的核心，优先处理长元素避免无法配对
usort($items, function($a, $b) {
    return $b['length'] - $a['length'];
});

// 3. 开始分组：为每个元素寻找最优的分组
$groups = [];
foreach ($items as $item) {
    $bestGroupIndex = -1;
    $minDiff = PHP_INT_MAX; // 记录与阈值的最小差值

    // 遍历现有分组，找到加入当前元素后总长度最接近limit的分组
    foreach ($groups as $index => $group) {
        $newTotal = $group['total_length'] + $item['length'];
        if ($newTotal <= $limit) {
            $diff = $limit - $newTotal;
            if ($diff < $minDiff) {
                $minDiff = $diff;
                $bestGroupIndex = $index;
            }
        }
    }

    if ($bestGroupIndex !== -1) {
        // 加入找到的最优分组
        $groups[$bestGroupIndex]['items'][] = $item['value'];
        $groups[$bestGroupIndex]['total_length'] += $item['length'];
    } else {
        // 没有合适的分组，新建一个
        $groups[] = [
            'items' => [$item['value']],
            'total_length' => $item['length']
        ];
    }
}

// 4. 按分组的总长度从高到低排序
usort($groups, function($a, $b) {
    return $b['total_length'] - $a['total_length'];
});

// 5. 将分组格式化为要求的字符串格式
$result = array_map(function($group) {
    return implode(' * ', $group['items']);
}, $groups);

// 输出最终结果
print_r($result);
?>

代码说明 #

1. 绑定元素与长度：先把每个元素和它的长度关联起来，避免重复计算strlen，提升效率。
2. 降序排序：优先处理长元素是贪心算法的关键，这样能避免长元素最后无法找到合适搭档的情况，确保最大程度利用阈值空间。
3. 寻找最优分组：对于每个元素，遍历现有分组，找到加入后总长度最接近阈值的分组（而不是随便找一个能容纳的），保证分组的总长度尽可能接近$limit。
4. 分组排序与格式化：最后按总长度排序分组，并将每组元素用*连接成字符串，得到你需要的输出格式。

运行这段代码，对于$limit=29的情况，会输出和你期望完全一致的结果。

内容的提问来源于stack exchange，提问作者kabus