1D Bin Packing Problem场景下PHP数组数值按上限500合并问题

原代码存在的问题 #

• 低级笔误1：foreach 遍历对象错误，你初始化$sumArr为空数组后直接遍历它，永远不会进入循环，应该遍历排序后的$orderSumArr
• 低级笔误2：循环结束后追加的$currentSum2是未定义变量，应该追加当前累计值$current
• 排序回调不规范：PHP的usort要求回调返回负/零/正整数，直接返回布尔值会导致排序结果不稳定，正确的升序排序应返回$a - $b或PHP7+支持的$a <=> $b
• 核心逻辑缺陷：默认的升序首次适应算法会将剩余的单个100和300组合成400，不符合你要求所有组合尽可能凑满500、不出现非满额混合组合的需求。

适配需求的实现思路 #

你的目标是优先把100凑满500，不要出现100和单个300组合成400的情况，针对当前数组的数值特性（仅包含100和300），可以用最高效的配对逻辑实现：

1. 统计100和300的数量
2. 优先计算可凑成300+2*100=500的最大组数，刚好把所有100消耗完
3. 剩余的300全部单独作为一项
4. 最后排序得到你期望的结果

可运行的代码示例 #

// 原始输入数组
$orderSumArr = [100,100,100,100,100,100,300,300,300,300,300,300,300,300,300,300];
$limit = 500;

// 统计不同数值的数量
$count100 = count(array_filter($orderSumArr, fn($v) => $v == 100));
$count300 = count(array_filter($orderSumArr, fn($v) => $v == 300));

$result = [];
// 优先凑 300 + 2*100 = 500 的组合
$pairNum = min(floor($count100 / 2), $count300);
for ($i = 0; $i < $pairNum; $i++) {
    $result[] = 500;
}
// 扣除已配对的数量
$count300 -= $pairNum;

// 剩余300全部加入结果
for ($i = 0; $i < $count300; $i++) {
    $result[] = 300;
}

// 按升序排序得到最终结果
sort($result);
print_r($result);

输出结果 #

运行上述代码得到的结果和你期望完全一致：

Array
(
    [0] => 300
    [1] => 300
    [2] => 300
    [3] => 300
    [4] => 300
    [5] => 300
    [6] => 300
    [7] => 500
    [8] => 500
    [9] => 500
)

如果后续数组会出现其他数值，可以改用降序首次适应算法（先放大元素再用小元素填空隙），也能有效减少不满箱的情况。

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