PHP simple packing items in boxes leads to unused space but there is capacity left

Question

I have a really simplistic approach to the packing of items as a PHP Script and I need to know if it's possible to minimize the leftover space inside the boxes where the items will be placed.

My code so far:

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

?>

Which leads to the Output:
Box 1 (330x330)
Item B (145x315)
Item A (100x295)
Item C (80x300)
The remaining capacity is: 9725

Box 2 (330x330)
Item H (70x300)
Item F (60x180)
Item D (60x160)
Item E (20x60)
Item G (30x50)
The remaining capacity is: 63600

Output:
<h3>Box 1 (330x330)</h3><div class="box" style="border:1px solid #333; box-sizing:border-box; width:330px; height:330px;"><div class="items"><div class="item" style="float:left;"><div class="item-name" style="border:1px solid #CCC; box-sizing:border-box; width:145px; height:315px;">Item B<span class="item-dimensions"> (145x315)</span></div></div><div class="item" style="float:left;"><div class="item-name" style="border:1px solid #CCC; box-sizing:border-box; width:100px; height:295px;">Item A<span class="item-dimensions"> (100x295)</span></div></div><div class="item" style="float:left;"><div class="item-name" style="border:1px solid #CCC; box-sizing:border-box; width:80px; height:300px;">Item C<span class="item-dimensions"> (80x300)</span></div></div></div></div><div class="remaining-capacity" style="clear:both;">The remaining capacity is: 9725</div><h3>Box 2 (330x330)</h3><div class="box" style="border:1px solid #333; box-sizing:border-box; width:330px; height:330px;"><div class="items"><div class="item" style="float:left;"><div class="item-name" style="border:1px solid #CCC; box-sizing:border-box; width:70px; height:300px;">Item H<span class="item-dimensions"> (70x300)</span></div></div><div class="item" style="float:left;"><div class="item-name" style="border:1px solid #CCC; box-sizing:border-box; width:60px; height:180px;">Item F<span class="item-dimensions"> (60x180)</span></div></div><div class="item" style="float:left;"><div class="item-name" style="border:1px solid #CCC; box-sizing:border-box; width:60px; height:160px;">Item D<span class="item-dimensions"> (60x160)</span></div></div><div class="item" style="float:left;"><div class="item-name" style="border:1px solid #CCC; box-sizing:border-box; width:30px; height:50px;">Item G<span class="item-dimensions"> (30x50)</span></div></div><div class="item" style="float:left;"><div class="item-name" style="border:1px solid #CCC; box-sizing:border-box; width:20px; height:60px;">Item E<span class="item-dimensions"> (20x60)</span></div></div></div></div><div class="remaining-capacity" style="clear:both;">The remaining capacity is: 64800</div>

Why won't Item E and G not fit into box 1 as well?

Answer 1

I have created a solution in OOPs way. I have created a Box class and a Package class.

Box class:

Initialize with box capacity and checked if item can fit into box or not and if it fit into box I decrease box capacity.

Package class:

It initializes with items and capacity, it has pack method which check no of items and add new box if required and check available space in boxes.

<?php
class Box
{
    protected $area;
    protected $capacity;
    protected $items;
    private int $availableWidth;

    public function __construct($capacity)
    {
        $this->capacity = $capacity;
        $this->area = $capacity * $capacity;
        $this->availableWidth = $capacity;
    }

    private function addItem($item)
    {
        $unUsedSpace = 0;

        $remain = $this->capacity - $item['height'];
        $item['space_left'] = [
            'height' => $remain,
            'width' => $this->availableWidth,
            'area' => $this->availableWidth * $remain
        ];
        $unUsedSpace = $this->availableWidth * $remain;
        $this->availableWidth -= $item['width'];
        $this->items[] = $item;
        $this->area = $this->area - $unUsedSpace;
    }

    private function addItemVertically($item)
    {
        $unUsedSpace = 0;

        $remain = $this->capacity - $item['height'];
        $item['space_left'] = [
            'height' => $remain,
            'width' => $this->availableWidth,
            'area' => $this->availableWidth * $remain
        ];
        $unUsedSpace = $this->availableWidth * $remain;
        $this->availableWidth -= $item['height'];

        $newItem = [
            'name' => $item['name'],
            'width' => $item['height'],
            'height' => $item['width'],
            'space_left' => $item['space_left']
        ];

        $this->items[] = $newItem;
        $this->area = $this->area - $unUsedSpace;
    }

    public function canItemFitInBox($item)
    {
        if (!empty($this->items)) {
            if ($this->availableWidth >= $item['width'] && $this->capacity >= $item['height']) {
                $this->addItem($item);
                return true;
            } elseif ($this->availableWidth >= $item['height'] && $this->capacity >= $item['width']) {
                $this->addItemVertically($item);
                return true;
            } else {
                return false;
            }
        }
        $this->addItem($item);
        return true;
    }

    public function canItemFitInLeftSpace($item)
    {
        foreach ($this->items as $space) {
            //compare left space height with item width
            $itemArea = $item['width'] * $item['height'];
            $spaceArea = $space['space_left']['area'];
            if (
                $space['space_left']['height'] >= $item['width']
                && $space['space_left']['width'] >= $item['height']
                && $spaceArea >= $itemArea
            ) {
                $space['space_left']['height'] -= $item['width'];
                $space['space_left']['width'] -= $item['height'];
                $space['space_left']['area'] -= $itemArea;
                $this->addItemVertically($item);
                return true;
            }
        }
        return false;
    }

    public function getItems()
    {
        return $this->items;
    }
}

class Package
{
    public array $boxes = [];
    public function __construct(public array $items, public int $capacity)
    {
        /* usort($this->items, function ($a, $b) {
            return $b['height'] - $a['height'];
        }); */
        usort($this->items, function ($a, $b) {
            $areaA = $a['width'] * $a['height'];
            $areaB = $b['width'] * $b['height'];
            return $areaB - $areaA;
        });
    }

    public function addNewBox()
    {
        $this->boxes[] = new Box($this->capacity);
    }

    public function checkSpaceInAvailableBoxes($item, $key)
    {
        foreach ($this->boxes as $box) {
            if ($box->canItemFitInBox($item)) {
                unset($this->items[$key]);
            } elseif ($box->canItemFitInLeftSpace($item)) {
                unset($this->items[$key]);
            }
        }
    }

    public function pack()
    {
        while (!empty($this->items)) {
            $this->addNewBox($this->capacity);
            foreach ($this->items as $key => $item) {
                $this->checkSpaceInAvailableBoxes($item, $key);
            }
        }

        return $this->boxes;
    }
}

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

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

        $boxItems = $box->getItems();
        foreach ($boxItems as $item) {
            $htmlFragments[] = '<div class="item" style="float:left;">';
            $htmlFragments[] = '<div class="item-name" style="writing-mode: vertical-rl;text-orientation: mixed; 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 ($boxItems 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 = 330;
$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
];

$package = new Package($items, $capacity);
$box = $package->pack();

echo generateHTML($box, $capacity);

Output

<h3>Box 1 (330x330)</h3><div class="box" style="border:1px solid #333; box-sizing:border-box; width:330px; height:330px;"><div class="items"><div class="item" style="float:left;"><div class="item-name" style="border:1px solid #CCC; box-sizing:border-box; width:145px; height:315px;">Item B<span class="item-dimensions"> (145x315)</span></div></div><div class="item" style="float:left;"><div class="item-name" style="border:1px solid #CCC; box-sizing:border-box; width:80px; height:300px;">Item C<span class="item-dimensions"> (80x300)</span></div></div><div class="item" style="float:left;"><div class="item-name" style="border:1px solid #CCC; box-sizing:border-box; width:70px; height:300px;">Item H<span class="item-dimensions"> (70x300)</span></div></div><div class="item" style="float:left;"><div class="item-name" style="border:1px solid #CCC; box-sizing:border-box; width:20px; height:60px;">Item E<span class="item-dimensions"> (20x60)</span></div></div><div class="item" style="float:left;"><div class="item-name" style="border:1px solid #CCC; box-sizing:border-box; width:30px; height:50px;">Item G<span class="item-dimensions"> (30x50)</span></div></div></div></div><div class="remaining-capacity" style="clear:both;">The remaining capacity is: 15525</div><h3>Box 2 (330x330)</h3><div class="box" style="border:1px solid #333; box-sizing:border-box; width:330px; height:330px;"><div class="items"><div class="item" style="float:left;"><div class="item-name" style="border:1px solid #CCC; box-sizing:border-box; width:100px; height:295px;">Item A<span class="item-dimensions"> (100x295)</span></div></div><div class="item" style="float:left;"><div class="item-name" style="border:1px solid #CCC; box-sizing:border-box; width:90px; height:200px;">Item J<span class="item-dimensions"> (90x200)</span></div></div><div class="item" style="float:left;"><div class="item-name" style="border:1px solid #CCC; box-sizing:border-box; width:60px; height:180px;">Item F<span class="item-dimensions"> (60x180)</span></div></div><div class="item" style="float:left;"><div class="item-name" style="border:1px solid #CCC; box-sizing:border-box; width:60px; height:160px;">Item D<span class="item-dimensions"> (60x160)</span></div></div><div class="item" style="float:left;"><div class="item-name" style="border:1px solid #CCC; box-sizing:border-box; width:40px; height:90px;">Item I<span class="item-dimensions"> (40x90)</span></div></div></div></div><div class="remaining-capacity" style="clear:both;">The remaining capacity is: 37400</div><h3>Box 3 (330x330)</h3><div class="box" style="border:1px solid #333; box-sizing:border-box; width:330px; height:330px;"><div class="items"><div class="item" style="float:left;"><div class="item-name" style="border:1px solid #CCC; box-sizing:border-box; width:160px; height:110px;">Item K<span class="item-dimensions"> (160x110)</span></div></div></div></div><div class="remaining-capacity" style="clear:both;">The remaining capacity is: 91300</div>