求产品数量数组的最大2产品组合数（PHP算法问题）

问题背景 #

需求为：从存储各产品数量的数组中，计算必须且只能选取2种产品的最大可能组合数（每次组合需从两种产品中各取1个）。现有算法在数组[1,1,4]时输出正确结果2，但在数组[4,4,2]时输出8，与预期结果5不符，需修正。

现有错误代码及执行过程 #

// array products
$group_iten = array (1,1,4); // 6 units in 3 products

// max and min per product
$max_min_products = 2;

// my algorithm
$i = 0;
$c = 0;
$counter = 0;
while ( true ) {
    // Sorts array in place by values in descending order
    rsort($group_iten);
    
    if ( $c < $max_min_products ) {
        
        $group_iten[$i] -= 1;
        
        $i++;
        $c++;
        $counter++;
    }
    else {
        $c = 0;
        $i = 0;
    }
    
    if ( min($group_iten) == 0 ) {
        unset($group_iten[$i]);
    }
    
    if ( count($group_iten) < $max_min_products )
        break;
}
print_r($counter);
// result = 2

现有代码执行异常案例

当输入数组为[4,4,2]时，现有代码输出8，但预期结果为5。手动模拟正确组合过程：

初始数组：[4,4,2]
第1次组合后：[3,3,2]（计数1）
第2次组合后：[2,2,2]（计数2）
第3次组合后：[1,1,2]（计数3）
第4次组合后：[1,0,1]（计数4）
第5次组合后：[0,0,0]（计数5）
无法继续组合，最终计数为5

现有代码错误分析 #

1. 计数逻辑错误：每次循环内连续递减两个元素并两次累加计数，错误地将单次组合拆分为两次计数，导致结果虚高。
2. 元素删除逻辑错误：删除0元素时使用的$i并非指向0元素的索引，导致错误删除有效元素，后续循环逻辑混乱。
3. 未正确过滤无效元素：未及时过滤掉数量为0的产品，导致后续循环处理无效数据。

修正后的算法代码 #

$group_item = [4, 4, 2];
$counter = 0;

// 先过滤掉初始数组中数量为0的产品
$group_item = array_filter($group_item, function($val) {
    return $val > 0;
});

// 循环直到剩余可组合的产品种类不足2种
while (count($group_item) >= 2) {
    // 降序排序，优先消耗数量最多的两种产品，保证组合数最大化
    rsort($group_item);
    
    // 两种产品各取1个，组合数+1
    $group_item[0]--;
    $group_item[1]--;
    $counter++;
    
    // 过滤掉数量减至0的产品
    $group_item = array_filter($group_item, function($val) {
        return $val > 0;
    });
}

echo $counter; // 输出5

修正代码验证 #

• 测试数组[1,1,4]：最终输出2，符合预期。
• 测试数组[4,4,2]：最终输出5，符合预期。

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