algorithm: How to arrange items using the minimum number of boxes based on their weight and quantity?

Question

There are n objects having different weights. We have to find the minimum number of boxes required to pack all weights where each box can have the maximum weight of K. Boxes can have any number of objects but weight should be less than or equal to given weight K.

All weights are less than or equal to K.

For example, let K= 10 and objects be {1,2,3,6,8} than minimum number of boxes required are 2 ,i.e, {8,2}, {1,3,6}

How should I approach this problem?

Answer 1

The Next Fit Decreasing (NFD) algorithm is an efficient method for arranging items into boxes, maximizing box utilization while minimizing the number of boxes used. To implement this algorithm, follow these steps:

1. Sort the items in descending order of weight. This ensures that heavier items are considered first during the packing process.

2. Initialize an array of boxes, each containing its remaining capacity (initially set to the box capacity).

3. Iterate through the sorted items and, for each item:

   • If the item's weight exceeds the box capacity, skip it as it cannot fit into any box.

   • Otherwise, start a nested loop to find a suitable box with enough remaining capacity to hold the item's weight.

   • If a valid box is found, place the item in it and update the remaining capacity of the box.

   • If no valid box is found, create a new box and place the item in it.

4. After processing all the items, you'll have a list of boxes with packed items and their respective remaining capacities.

<?php
   /**
     * Arranges items into boxes using the Next Fit Decreasing (NFD) algorithm.
     * 
     * This function takes an array of items and a box capacity and arranges the items into boxes
     * using the Next Fit Decreasing (NFD) algorithm, which sorts the items in descending order of weight
     * and then places them in boxes one by one, creating a new box if the current box is unable to hold the entire item.
     * 
     * @param array $items An array of items to be arranged in boxes. Each item is represented as an associative array
     *                     with the following structure: ['name' => string, 'qty' => int, 'weight' => int].
     * @param int   $boxCapacity The maximum weight capacity of each box.
     * @return array Returns an associative array with two keys:
     *               - 'boxes': An array containing the arranged items in boxes. Each box is represented as an associative
     *                          array with the following structure: ['items' => array, 'remaining_capacity' => int].
     *               - 'skippedItems': An array containing the items that were skipped because their weight exceeded
     *                                 the box capacity. Each skipped item is represented as an associative array with
     *                                 the same structure as the items in the input array.
     */
    public function arrangeItemsInBoxes($items, $boxCapacity)
    {
        // Sort items in descending order of weight
        usort($items, function ($a, $b) {
            return $b['weight'] - $a['weight'];
        });

        $boxes = [['items' => [], 'remaining_capacity' => $boxCapacity]]; // Initialize the first box
        $skipedItems = [];

        foreach ($items as $item) {
            if ($item['weight'] > $boxCapacity) {
                // Skip the item if its weight exceeds the box capacity
                $skipedItems[] = $item;
                continue;
            }

            $qtyLeft = $item['qty'];

            while ($qtyLeft > 0) {
                $boxIndex = $this->findValidBoxIndex($boxes, $item['weight']);
                if ($boxIndex < 0) {
                    $boxIndex = count($boxes);
                    $boxes[] = ['items' => [], 'remaining_capacity' => $boxCapacity];
                }
                $box = &$boxes[$boxIndex];
                $remainingBoxCapacity = &$box['remaining_capacity'];

                $fitQty = min($qtyLeft, floor($remainingBoxCapacity / $item['weight']));
                $fittedWeight = $fitQty * $item['weight'];
                $box['items'][] = [
                    'name' => $item['name'],
                    'qty' => $fitQty,
                    'fitted_weight' => $fittedWeight,
                ];

                $remainingBoxCapacity -= $fittedWeight;

                $qtyLeft -= $fitQty;
            }
        }

        return ['boxes' => $boxes, 'skipedItems' => $skipedItems];
    }

    /**
     * Finds the index of a valid box in the given array of boxes based on their remaining capacity.
     *
     * This function searches through the array of boxes to find a box with sufficient remaining capacity
     * to accommodate the given weight. It returns the index of the first valid box found.
     *
     * @param array $boxes An array containing boxes with their respective 'remaining_capacity'.
     *                     Each box is represented as an associative array with the following structure:
     *                     ['remaining_capacity' => int]
     * @param int $weight The weight of the item that needs to be placed in a box.
     *
     * @return int Returns the index of the first box with sufficient remaining capacity to hold the item's weight,
     *             or -1 if no valid box is found.
     */
    function findValidBoxIndex($boxes, $weight)
    {
        $result = -1;
        foreach ($boxes as $key => $box) {
            if ($box['remaining_capacity'] >= $weight) {
                $result = $key;
                break;
            }
        }

        return $result;
    }

just pass items and max capacity of box as input as like below

$items = [
    ['name' => 'Item 1', 'weight' => 20, 'qty' => 6],
    ['name' => 'Item 2', 'weight' => 10, 'qty' => 8],
    ['name' => 'Item 3', 'weight' => 4, 'qty' => 7],
    ['name' => 'Item 4', 'weight' => 10, 'qty' => 1],
];

$startTime = microtime(true);
$result = $this->arrangeItemsInBoxes($items, 40);
$endTime = microtime(true);
$executionTime = ($endTime - $startTime) * 1000; // Convert to milliseconds

output of above items input data

Som of total boxes 6 Sum Of Items weight is 238 & taken time 0.022172927856445 & skipped items 0
Box 0 (Remaining Capacity: 0): - Item 1 (Fitted Qty: 2 & Fitted weight: 40)
Box 1 (Remaining Capacity: 0): - Item 1 (Fitted Qty: 2 & Fitted weight: 40)
Box 2 (Remaining Capacity: 0): - Item 1 (Fitted Qty: 2 & Fitted weight: 40)
Box 3 (Remaining Capacity: 0): - Item 2 (Fitted Qty: 4 & Fitted weight: 40)
Box 4 (Remaining Capacity: 0): - Item 2 (Fitted Qty: 4 & Fitted weight: 40)
Box 5 (Remaining Capacity: 2): - Item 4 (Fitted Qty: 1 & Fitted weight: 10) - Item 3 (Fitted Qty: 7 & Fitted weight: 28)

I hope this one helps to you.

Happy Coding :)