# Thread: Packing Math Problem (PHP Experts Only)

1. ## Packing Math Problem (PHP Experts Only)

I'm trying to create a class that will pack products into boxes.

There are different products and box sizes.

If more than one product then they needed to be fitted in a box that will hold both items. if a box is not big enough then the order must be split into a new box.

This problem is also called:

3D Bin Packer
The Knapsack Problem

I have not found any PHP examples. This is what I have got so far:

Box class
PHP Code:
``` final class Box {     private \$packaging_id;     private \$length;     private \$width;     private \$height;     private \$weight;     private \$product = array();          function __construct(\$packaging_id, \$length, \$width, \$height, \$weight) {         \$this->packaging_id = \$packaging_id;         \$this->length = \$length;         \$this->width = \$width;         \$this->height = \$height;     }          function addProduct(\$product) {         \$this->product[] = \$product;     }          function check(\$product) {         \$status = TRUE;                  if (\$product['width'] > \$width) {                  }     }     function getPrice() {         \$price = 0;                  foreach (\$this->product as \$product) {             \$price += \$product['price'];         }                  return \$price;     }          function getWeight() {         \$weight = 0;                  foreach (\$this->product as \$product) {             \$weight += \$product['weight'];         }                  return \$weight;     } }  ```

Packaging Class
PHP Code:
``` final class Packaging {     private \$box = array();              function __construct(\$product, \$package) {         for (\$i = 0; \$i < count(\$product); \$i++) {             \$product[\$i]['volume'] = \$product[\$i]['length'] * \$product[\$i]['width'] * \$product[\$i]['height'];         }         for (\$i = 0; \$i < count(\$package); \$i++) {             \$package[\$i]['volume'] = \$package[\$i]['length'] * \$package[\$i]['width'] * \$package[\$i]['height'];         }                  \$sort_order = array();                 foreach (\$package as \$key => \$value) {               \$sort_order[\$key] = \$value['volume'];         }         array_multisort(\$sort_order, SORT_ASC, \$package);                          foreach (\$product as \$key => \$value) {             if ((\$package[\$i]['volume'] > \$product[\$i]['volume']) && (\$package[\$i]['weight'] > \$product[\$i]['weight'])) {                 \$box[\$k] = array(                     'packaging_id'    => \$package[\$i]['packaging_id'],                      'length'        => \$package[\$i]['length'],                     'width'         => \$package[\$i]['width'],                     'height'        => \$package[\$i]['height'],                     'product'       => \$product[\$i],                     'volume'        => \$package[\$i]['volume'] - \$product[\$i]['volume'],                     'weight'        => \$package[\$i]['weight'] - \$product[\$i]['weight']                 );                                  \$k++;                                  continue;             }                                      for (\$j = 0; \$j < count(\$package); \$j++) {                 if (\$package[\$i]['volume'] < \$product['volume']) {                     continue;                 }                              if (\$package[\$i]['weight'] < \$product['weight']) {                     continue;                 }             }         }                  \$box = array();                  \$k = 0;                  for (\$i = 0; \$i < count(\$product); \$i++) {             if (!\$box) {                 for (\$j = 0; \$j < count(\$package); \$j++) {                     if (\$package[\$i]['volume'] < \$product[\$i]['volume']) {                         continue;                     }                                          if (\$package[\$i]['weight'] < \$product[\$i]['weight']) {                         continue;                     }                                          if ((\$package[\$i]['volume'] > \$product[\$i]['volume']) && (\$package[\$i]['weight'] > \$product[\$i]['weight'])) {                         \$box[\$k] = array(                             'packaging_id'       => \$package[\$i]['packaging_id'],                              'length'           => \$package[\$i]['length'],                             'width'            => \$package[\$i]['width'],                             'height'           => \$package[\$i]['height'],                             'product'          => \$product[\$i],                             'remaining_volume' => \$package[\$i]['volume'] - \$product[\$i]['volume'],                             'remaining_weight' => \$package[\$i]['weight'] - \$product[\$i]['weight']                         );                                                  \$k++;                     }                 }             } else {                 for (\$j = 0; \$j < count(\$box); \$j++) {                                                   }             }         }     }     function addItem(\$length, \$width, \$height, \$weight, \$price = 0) {         if ((float)\$weight < 1.0) {             \$weight = 1;         } else {             \$weight = round(\$weight, 1);         }                \$index = \$this->items_qty;                 \$this->item[\$index]['length'] = (\$length ? (string)\$length : 0);         \$this->item[\$index]['width'] = (\$width ? (string)\$width : 0);         \$this->item[\$index]['height'] = (\$height ? (string)\$height : 0);         \$this->item[\$index]['weight'] = (\$weight ? (string)\$weight : 0);         \$this->item[\$index]['price'] = \$price;                \$this->items_qty++;     } }  ```

Data
PHP Code:
``` \$product_data = array(); \$product_data[] = array(     'product_id'    => 1,     'name'          => 'Product 1',     'quantity'      => 2,     'price'         => 10,     'length'        => 12,     'width'         => 6,     'height'        => 6,     'weight'        => 1,     'ready_to_ship' => false ); \$product_data[] = array(     'product_id'    => 2,     'name'          => 'Product 2',     'quantity'      => 1,     'price'         => 10,     'length'        => 5,     'width'         => 6,     'height'        => 6,     'weight'        => 1,     'ready_to_ship' => false ); \$product_data[] = array(     'product_id'    => 3,     'name'          => 'Product 3',     'quantity'      => 1,     'price'         => 10,     'length'        => 9,     'width'         => 14,     'height'        => 12,     'weight'        => 1,     'ready_to_ship' => false ); \$product_data[] = array(     'product_id'    => 3,     'name'          => 'Product 3',     'quantity'      => 1,     'price'         => 10,     'length'        => 14,     'width'         => 16,     'height'        => 20,     'weight'        => 1,     'ready_to_ship' => false ); \$package_data = array();                           \$package_data[] = array(     'packaging_id' => 1,     'name'         => '9x8x9',     'description'  => '9x8x9',     'length'       => 9,     'width'        => 8,     'height'       => 9,     'weight'       => 5 ); \$package_data[] = array(     'packaging_id' => 2,     'name'         => '12x14x13',     'description'  => '12x14x13',     'length'       => 12,     'width'        => 14,     'height'       => 13,     'weight'       => 10, ); \$package_data[] = array(     'packaging_id' => 3,     'name'         => '18x19x22',     'description'  => '18x19x22',     'length'       => 18,     'width'        => 19,     'height'       => 22,     'weight'       => 25 ); \$package_data[] = array(     'packaging_id' => 3,     'name'         => '25x29x28',     'description'  => '25x29x28',     'length'       => 25,     'width'        => 29,     'height'       => 28,     'weight'       => 25 ); \$package_data[] = array(     'packaging_id' => 3,     'name'         => '36x30x38',     'description'  => '36x30x38',     'length'       => 36,     'width'        => 30,     'height'       => 38,     'weight'       => 25 ); error_reporting(E_ALL); \$packaging = new Packaging(\$product_data, \$package_data); echo '<pre>'; //print_r(\$package_data); //print_r(\$empty_box_data); print_r(\$packaging); echo '</pre>';  ```

2. Weight is normally a consideration in this algorithm, yet you do not mention it. Do you want to consider a maximum weight per `bin` ?

3. yes

each packaging has a max weight limit.

4. updated code:

PHP Code:
``` final class Box {     private \$packaging_id;     private \$length;     private \$width;     private \$height;     private \$max_weight;     private \$product = array();          function __construct(\$packaging_id, \$length, \$width, \$height, \$max_weight) {         \$this->packaging_id = \$packaging_id;         \$this->length = \$length;         \$this->width = \$width;         \$this->height = \$height;         \$this->max_weight = \$max_weight;     }          function addProduct(\$product) {         \$this->product[] = \$product;     }          function getWeightTotal() {         \$weight = 0;                  foreach (\$this->product as \$product) {             \$weight += \$product['weight'];         }                  return \$weight;     }          function getPriceTotal() {         \$price = 0;                  foreach (\$this->product as \$product) {             \$price += \$product['price'];         }                  return \$price;     } } final class Packaging {     private \$box = array();              function __construct(\$product, \$package) {         for (\$i = 0; \$i < count(\$product); \$i++) {             \$product[\$i]['volume'] = \$product[\$i]['length'] * \$product[\$i]['width'] * \$product[\$i]['height'];         }         for (\$i = 0; \$i < count(\$package); \$i++) {             \$package[\$i]['volume'] = \$package[\$i]['length'] * \$package[\$i]['width'] * \$package[\$i]['height'];         }                  \$sort_order = array();                 foreach (\$package as \$key => \$value) {               \$sort_order[\$key] = \$value['volume'];         }         array_multisort(\$sort_order, SORT_ASC, \$package);                 foreach (\$product as \$key => \$value) {             if ((\$package[\$i]['volume'] > \$product[\$i]['volume']) && (\$package[\$i]['weight'] > \$product[\$i]['weight'])) {                 \$box[\$k] = array(                     'packaging_id'    => \$package[\$i]['packaging_id'],                      'length'        => \$package[\$i]['length'],                     'width'         => \$package[\$i]['width'],                     'height'        => \$package[\$i]['height'],                     'product'       => \$product[\$i],                     'volume'        => \$package[\$i]['volume'] - \$product[\$i]['volume'],                     'weight'        => \$package[\$i]['weight'] - \$product[\$i]['weight']                 );                                  \$k++;                                  continue;             }                                      for (\$j = 0; \$j < count(\$package); \$j++) {                 if (\$package[\$i]['volume'] < \$product['volume']) {                     continue;                 }                              if (\$package[\$i]['weight'] < \$product['weight']) {                     continue;                 }             }         }     } }         \$product_data = array(); \$product_data[] = array(     'product_id'    => 1,     'name'          => 'Product 1',     'quantity'      => 2,     'price'         => 10,     'length'        => 12,     'width'         => 6,     'height'        => 6,     'weight'        => 1, ); \$product_data[] = array(     'product_id'    => 2,     'name'          => 'Product 2',     'quantity'      => 1,     'price'         => 10,     'length'        => 5,     'width'         => 6,     'height'        => 6,     'weight'        => 1, ); \$product_data[] = array(     'product_id'    => 3,     'name'          => 'Product 3',     'quantity'      => 1,     'price'         => 10,     'length'        => 9,     'width'         => 14,     'height'        => 12,     'weight'        => 1, ); \$product_data[] = array(     'product_id'    => 3,     'name'          => 'Product 3',     'quantity'      => 1,     'price'         => 10,     'length'        => 14,     'width'         => 16,     'height'        => 20,     'weight'        => 1, ); \$package_data = array();                           \$package_data[] = array(     'packaging_id' => 1,     'name'         => '9x8x9',     'description'  => '9x8x9',     'length'       => 9,     'width'        => 8,     'height'       => 9,     'max_weight'   => 5 ); \$package_data[] = array(     'packaging_id' => 2,     'name'         => '12x14x13',     'description'  => '12x14x13',     'length'       => 12,     'width'        => 14,     'height'       => 13,     'max_weight'   => 10, ); \$package_data[] = array(     'packaging_id' => 3,     'name'         => '18x19x22',     'description'  => '18x19x22',     'length'       => 18,     'width'        => 19,     'height'       => 22,     'max_weight'   => 25 ); \$package_data[] = array(     'packaging_id' => 3,     'name'         => '25x29x28',     'description'  => '25x29x28',     'length'       => 25,     'width'        => 29,     'height'       => 28,     'max_weight'   => 25 ); \$package_data[] = array(     'packaging_id' => 3,     'name'         => '36x30x38',     'description'  => '36x30x38',     'length'       => 36,     'width'        => 30,     'height'       => 38,     'max_weight'   => 25 ); error_reporting(E_ALL); \$packaging = new Packaging(\$product_data, \$package_data); echo '<pre>'; print_r(\$packaging); echo '</pre>';  ```

5. How many items would typically go into a shipping? If the number is relatively low, you could brute-force it.

7. how to brute force though?

Would it allow the pack to be flip to its side if there is remaining room?

8. Here is a fairly well commented process in C, maybe you could attempt to transpose it to PHP.

9. Originally Posted by blueyon
how to brute force though?
Basically calculate all possible combinations. Then sort them according to some set of rules and pick the highest ranking. A rule could for example be to minimise the number of packages. You can apply the sorting algorithm on the fly, so that you don't need to store all the combinations in memory. Writing an algorithm to calculate the combinations should be relatively simple.

Originally Posted by blueyon
Would it allow the pack to be flip to its side if there is remaining room?
To support this, you'll have to add a choice of orientation to the set of combinations. If all your items are rectangular, you'll have three variations for each, in a 3d space.

10. I definitely tackle atleast some of this problem in SQL.

11. no shopping cart system I have found have a 3D binpacking system.

If this coding problem could be solved it would help giving the correct shipping amounts when shipping calculations are made. It could actually reduce the cost of customers orders by giving the correct number of packages being shipped.

12. Originally Posted by blueyon
no shopping cart system I have found have a 3D binpacking system.

If this coding problem could be solved it would help giving the correct shipping amounts when shipping calculations are made. It could actually reduce the cost of customers orders by giving the correct number of packages being shipped.
3D Tetris

13. Originally Posted by blueyon
no shopping cart system I have found have a 3D binpacking system.
Hmm thinking about why a 3d binpacking system hasn't been developed.

Possibly because they could be more trouble than they're worth?

If having to pack the manually, then either the packer would need to know what the the solution the packer programme solved it. Especially if allowing rotations, there is only 3 possible, but still with multiple products being packed into a single box seems like it could be time consuming, if it was too good at efficiently packing.

Think it would need to be simplified when there is more than 1 product to pack. A single product can be easily rotated to fit an appropriate box.

14. Originally Posted by Ren
If having to pack the manually, then either the packer would need to know what the the solution the packer programme solved it.
I suppose that the program could generate instructions for the packer.

But you're right. The web shops I've made, either had free shipping or had a fixed cost for shipping. The cost were simply calculated into the price. After all - If you have to ship an additional package, it's usually because there was a bigger sale, and thus bigger revenue.

15. Definitely a problem to solve at either end I think.

Work out the all the combinations of products that fit into each package.

For the individual products all the packaging solutions would be something like..

Returns all the products and which boxes they fit in
Code:
```SELECT product_id, box_id
FROM product p INNER JOIN box b
ON (p.length < b.length AND p.width < b.width AND p.height < b.height)
OR (p.height < b.length AND p.length < b.width AND p.width < b.height)
OR (p.width < b.length AND p.height < b.width AND p.length < b.height)```
For every two products and which boxes they fit in, assuming they are stacked on top of each other...
(would need more OR conditions to take into account rotations or other packing configurations)
Code:
```SELECT p1.product_id, p2.product_id, b.box_id
FROM
product p1, product p2, box b
WHERE p1.product_id <= p2.product_id
AND
MAX(p1.width, p2.width) < b.width
AND
MAX(p1.length, p2.length) < b.length
AND
p1.height + p2.height < b.height```
And so on...

Once have the all that predetermined (can be done at new product, or new packaging time) it just seems a mapping of the a shoppers basket to boxes, which I think is simple iterative process, without any 3D math.

Code:
```while have products-to-pack
{
partial-solution = getPackingSolutionWhichHasMost(products-to-pack)
Remove partial-solution-packed-products from products-to-pack
}```

16. Actually the latter problem could possibly done with Lucene or something... maybe. *Odd on the toilet thinking...

If get Lucene to index documents with packaging instructions configurations like...

Code:
```use box #1
orange
orange
orange
orange```
A shopping list would look like

Code:
```orange
orange
orange```
And asking Lucene for packaging instructions most like our shopping list, and picking the most similar would give at least a partial solution.

Well don't need Lucene, just the knowledge of inverse document frequencies, cosine similarity, and so forth. And treating the shopping lists and packing solutions as vectors.

17. ok I think I have come up with a brute force method.

1. Go through the list of products and filter out all the products that are 2 big to fit in any of the boxes and make them as there own box. e.g a table might be to big to fit in any standard box.

2. Go through the remaining products and put the products in the box. find the box that accepts the most products.

3. Remove the products in the box from the product list and start the step 2 again until there are no products left.

18. Available solutions already exist that I presume will do much better than any ones created in this thread. Please consult them and try to understand them before attempting to solve this problem. My previous reply has a link to a PHP class which should do what you want.

Finally, to anyone suggesting a brute-force algorithm: NO.

19. Originally Posted by Peter Goodman
Available solutions already exist that I presume will do much better than any ones created in this thread. Please consult them and try to understand them before attempting to solve this problem. My previous reply has a link to a PHP class which should do what you want.

Finally, to anyone suggesting a brute-force algorithm: NO.
The link you posted just works on one dimension, filesizes.. where the OP is working in 3 possibly 4.
width, height, length & weight.

Brute force is fine if can solve it once, and look up answers per request, as I outlined.

Pretty sure that the phpclass will be brute forcing it per request.... though can't see the source code as need to be registered.

20. Just interested if could solve it with the lucene method..

Instead of words/terms have product_ids or skus, and instead of term frequencies have quantities.

Here's is a proof concept.. ish.

The theory/math needs going over as done it from memory.

But given a list of packing solutions, (ie all combinations of products than can fit into a particular package) and precomputed their vectors....

PHP Code:
``` <?phpclass Vector{    static function dotProduct(array \$a, array \$b)    {        \$r = 0;        foreach(\$a as \$i => \$ai)            if (isset(\$b[\$i]))                \$r += \$ai * \$b[\$i];        return \$r;    }    static function length(array \$a)    {        return sqrt(array_reduce(\$a, function(\$r, \$i) { return \$r + (\$i * \$i); }, 0));    }    static function div(array \$a, \$n)    {        return array_map(function(\$i) use (\$n) { return \$i / \$n; }, \$a);    }    static function normalize(array \$a)    {        return self::div(\$a, self::length(\$a));    }}class Packer{    protected \$solutions;    protected \$vectors;    function __construct(\$solutions, \$vectors)    {        \$this->solutions = \$solutions;        \$this->vectors = \$vectors;    }    function pack(array \$productsToPack)    {        \$solution = array();        while (\$productsToPack)        {            \$r = array();            \$productsToPackVector = Vector::normalize(\$productsToPack);echo 'Packing ', json_encode(\$productsToPack), "\n";            foreach(\$this->vectors as \$solutionId => \$vector)            {                \$similarity = Vector::dotProduct(\$productsToPackVector, \$vector);echo ' -> ', json_encode(\$this->solutions[\$solutionId]), ' ', \$similarity, "\n";                if (\$similarity > 0)                    \$r[\$solutionId] = \$similarity;            }            if (\$r)            {                arsort(\$r);                list(\$partialSolution, \$similarity) = each(\$r);echo ' Packed using ', json_encode(\$this->solutions[\$partialSolution]), ' ', \$similarity, "\n";                foreach(\$this->solutions[\$partialSolution] as \$product => \$quantity)                    if (isset(\$productsToPack[\$product]))                    {                        \$productsToPack[\$product] -= \$quantity;                        if (0 >= \$productsToPack[\$product])                            unset(\$productsToPack[\$product]);                    }                \$solution[] = \$partialSolution;            }            else                throw new Exception('Unable to pack '.json_encode(\$productsToPack));        }        return \$solution;    }}\$products = array(    'orange',    'apple',    'banana',);\$numberOfProducts = count(\$products);\$packingSolutions = array();\$packingSolutions[0] = array('orange' => 1);                    // can fit 1 orange in\$packingSolutions[1] = array('orange' => 4);                    // can fit 4 oranges in\$packingSolutions[2] = array('apple' => 1);                        // can fit 1 apple in\$packingSolutions[3] = array('apple' => 3);                        // can fit 3 apples in\$packingSolutions[4] = array('banana' => 1);                    // can fit 1 banana in\$packingSolutions[5] = array('orange' => 2, 'apple' => 2);        // can fit 2 oranges & 2 apples in\$packingVectors = array();foreach(\$packingSolutions as \$packingSolutionId => \$packedProducts)    \$packingVectors[\$packingSolutionId] = Vector::normalize(\$packedProducts);    \$packer = new Packer(\$packingSolutions, \$packingVectors);\$basket = array();\$basket['orange'] = 2;\$basket['apple'] = 3;\$solution = \$packer->pack(\$basket);echo "\n", 'Packing solution', "\n";foreach(\$solution as \$solutionId)    echo json_encode(\$packingSolutions[\$solutionId]), "\n"; ```
PS the math definitely needs checking...

21. I don't understand much about the code you have posted above but creating a list of available vectors after each product is added sounds like a good idea.

you can run through the avaliable vectors to see if a product fits.

22. Originally Posted by blueyon
I don't understand much about the code you have posted above but creating a list of available vectors after each product is added sounds like a good idea.

you can run through the avaliable vectors to see if a product fits.
If have 2 products called x, and y.

Every list of products can been seen as a point on a 2 dimensional graph.

2x's and 1y... would be the point (2, 1) on the graph
3x's and 0y would be (3, 0) and so on.

Now having two points, one is productsToPack and another is productsWeCanPackIntoAParticularBox.

If draw lines from origin (0,0) to both, the angle between them represents how similar they are, the smaller the angle, the more similar the both product-lists are.

24. Originally Posted by blueyon
If correctly pregenerated all possible contents for each box, the above routine should use it.

Eg in the code above, there is a box that will take 2 oranges and 2 apples....

PHP Code:
``` \$packingSolutions[5] = array('orange' => 2, 'apple' => 2);    // can fit 2 oranges & 2 apples in  ```
So if ask for 4 oranges and 3 apples...

PHP Code:
``` \$basket = array(); \$basket['orange'] = 4; \$basket['apple'] = 3; \$solution = \$packer->pack(\$basket);  ```
It says to use 2 of the boxes than can hold 2 oranges & 2 apples.

Code:
```{"orange":2,"apple":2}
{"orange":2,"apple":2}```

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•