Calculating maximum package size (in PHP)

Question

Working with PHP for this.

From a given set of items, each with its own weight, I need to automatically calculate the most effective way to package the items into 100 lbs packages (max package weight of 100 lbs is static, but can be changed in the future). A single package cannot exceed the maximum specified.

As an example, I have 5 items - with a total weight of 254 lbs:

• Item 1 -> 51 lbs
• Item 2 -> 28 lbs
• Item 3 -> 73 lbs
• Item 4 -> 51 lbs
• Item 5 -> 51 lbs

One would assume that 254 lbs would require 3 x 100 lbs packages. This example purposely demonstrates that this is not always the case. Certain item configurations could not work well together. This example would require 4 x 100 lbs packages in its optimal configuration.

The item count and weights are completely variable, and no single item will exceed 100 lbs.

What would be the most optimal way to achieve this?

Answer 1

The problem you are describing is called the Bin Packing Problem. No-one knows the optimal way to solve it. If they did they would be able to prove P=NP or P!=NP - one of the big open questions in computing.

The Wikipedia page includes references to some example algorithms - first fit algorithm, best fit decreasing, first fit decreasing. In general a fast way to solve this problem is to not attempt find the optimal solution, but to find a good approximation. The 'decreasing' refers to it being a good idea to start with packing the largest, most awkward elements first, and then fill the gaps with the small elements at the end. This is actually similar to how most humans typically approach this problem.

For the size of problem you gave in your example, it would be simple to find the optimal solution just by checking all the possible permutations, but obviously that won't be very efficient for larger examples.

Answer 2

The problem is actually the same as discussed here:

http://stackoverflow.com/questions/1982906/convert-function-from-recursion-to-iteration

Blind search method is to apply every combination of packages which would create an algorithm of order N!, If you've only got small numbers of items that's not a big problem (5 items gives just 120 combinations to search - but 10 requires over 3.6 million)

As per my post there, see

http://en.wikipedia.org/wiki/Travelling_salesman_problem

For descriptions of non-exhaustive algorithms.

C.

Answer 3

For those who are interested, here is the code I wrote to solve my question:

    //Loop thru cart items - adding weights to packages
    foreach((array)$this->cart_items as $cart_item) {
        for ($i = 0; $i < $cart_item->quantity; $i++) {

            $itemWeight = $cart_item->weight;    //Get current item weight
            $currWeight += $itemWeight;             //Add item weight to active package

            if ($currWeight > 100){                      //Max weight reached for active package

                $currWeight -= $itemWeight;         //Remove item from current package, too heavy
                $loopPack = 0;                                  
                $itemUsed = false;

                //Check if an existing package can take the item
                while (($loopPack != $packageCount) or ($itemUsed = false)) {
                    if ($packages[$loopPack] + $itemWeight < 100) {
                        $packages[$loopPack] += $itemWeight;
                        $itemUsed = true;
                    }
                    $loopPack++;
                }

                //if the item didn't fit in an existing package, create a new package for it
                if ($itemUsed == false) {
                    $packageCount++;
                    $packages[$packageCount-1] = $currWeight;
                    $currWeight = $cart_item->weight;            //Put unused item back in active package   
                }

            }
        }
    }
    //The remainder becomes a package
    $packageCount++;
    $packages[$packageCount-1] = $currWeight;

    print_r($packages);