PHP装箱脚本空间浪费疑问：Item E与G为何无法放入Box1？

我编写了一个简易的PHP物品装箱脚本，目标是减少箱子剩余空间。当前逻辑为：先按物品面积降序排序，再将物品横向堆叠放入箱子，若当前箱子宽度不足则新建箱子。但运行后发现Item E（20x60）和Item G（30x50）明明有剩余空间却没放进Box1，想知道原因。

现有代码 #

<?php
$GLOBALS['capacity'] = 330;

function PackIt($capacity, $items)
{
    usort($items, function ($a, $b) {
        $areaA = $a['width'] * $a['height'];
        $areaB = $b['width'] * $b['height'];
        return $areaB - $areaA;
    });

    $boxes = [];
    $currentBox = ['width' => 0, 'height' => 0, 'items' => []];

    foreach ($items as $item) {
        $itemWidth = $item['width'];
        $itemHeight = $item['height'];

        // Check if the item fits in the current box
        if ($itemWidth <= $capacity - $currentBox['width']) {
            $currentBox['items'][] = $item;
            $currentBox['width'] += $itemWidth;
            $currentBox['height'] = max($currentBox['height'], $itemHeight);
        } else {
            // If the item doesn't fit, create a new box and add the item
            $boxes[] = $currentBox;
            $currentBox = ['width' => $itemWidth, 'height' => $itemHeight, 'items' => [$item]];
        }
    }

    $boxes[] = $currentBox;

    return $boxes;
}

function generateHTML($boxes)
{
    $capacity = $GLOBALS['capacity'];
    $htmlFragments = [];

    foreach ($boxes as $boxIndex => $box) {
        $htmlFragments[] = '<h3>Box ' . ($boxIndex + 1) . ' ('.$capacity.'x'.$capacity.')</h3>';
        $htmlFragments[] = '<div class="box" style="border:1px solid #333; box-sizing:border-box; width:' . $capacity . 'px; height:' . $capacity . 'px;">';
        $htmlFragments[] = '<div class="items">';

        foreach ($box['items'] as $item) {
            $htmlFragments[] = '<div class="item" style="float:left;">';
            $htmlFragments[] = '<div class="item-name" style="border:1px solid #CCC; box-sizing:border-box; width:' . $item['width'] . 'px; height:' . $item['height'] . 'px;">' . $item['name'] . '<span class="item-dimensions"> (' . $item['width'] . 'x' . $item['height'] . ')</span></div>';
            $htmlFragments[] = '</div>';
        }

        $htmlFragments[] = '</div>';

        // Calculate remaining capacity for the box
        $boxArea = 330 * 330;
        $occupiedArea = 0;

        foreach ($box['items'] as $item) {
            $itemWidth = $item['width'];
            $itemHeight = $item['height'];
            $occupiedArea += $itemWidth * $itemHeight;
        }

        $htmlFragments[] = '</div>';
        $remainingCapacity = $boxArea - $occupiedArea;
        $htmlFragments[] = '<div class="remaining-capacity" style="clear:both;">The remaining capacity is: ' . $remainingCapacity . '</div>';
    }


    return implode('', $htmlFragments);
}

$capacity = $GLOBALS['capacity'];
$items = [
    ['name' => 'Item A', 'width' => 100, 'height' => 295],
    ['name' => 'Item B', 'width' => 145, 'height' => 315],
    ['name' => 'Item C', 'width' => 80, 'height' => 300],
    ['name' => 'Item D', 'width' => 60, 'height' => 160],
    ['name' => 'Item E', 'width' => 20, 'height' => 60],
    ['name' => 'Item F', 'width' => 60, 'height' => 180],
    ['name' => 'Item G', 'width' => 30, 'height' => 50],
    ['name' => 'Item H', 'width' => 70, 'height' => 300],
    // ... more items
];

$boxes = PackIt($capacity, $items);

// Generate HTML
$htmlOutput = generateHTML($boxes);

echo $htmlOutput;

?>

运行输出 #

Box 1 (330x330) #

• Item B (145x315)
• Item A (100x295)
• Item C (80x300)
  剩余空间：9725

Box 2 (330x330) #

• Item H (70x300)
• Item F (60x180)
• Item D (60x160)
• Item E (20x60)
• Item G (30x50)
  剩余空间：63600

疑问解答 #

核心原因是你的装箱逻辑只检查了箱子的横向剩余宽度，完全忽略了纵向可以利用的空隙：

1. Box1中已放置物品的总宽度为 145+100+80=325，箱子宽度是330，剩余横向宽度仅为5。
2. 代码中的判断条件 if ($itemWidth <= $capacity - $currentBox['width']) 仅验证物品宽度能否塞进横向剩余空间，Item E宽度20、Item G宽度30都远大于5，因此直接判定无法放入Box1，被分到了Box2。
3. 虽然Box1还有9725的剩余面积，但这些面积分布在已放置物品的下方（比如Item A下方有 330-295=35 的高度空间，宽度100；Item C下方有 330-300=30 的高度空间，宽度80），但你的代码没有追踪这些纵向空隙，自然不会尝试把小物品放进这些区域。

优化思路 #

如果想利用这些剩余空间，需要将当前的一维横向堆叠逻辑改为二维装箱逻辑，比如：

• 追踪箱子内的可用矩形区域，每次放置物品后更新这些区域；
• 尝试将物品放入现有箱子的所有可用空隙，而非仅看横向总宽度；
• 参考经典二维装箱算法，比如下一个适应算法（Next Fit）、最佳适应算法（Best Fit）的二维变种。

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