What mathematical formula would I use to maximize two-dimensional storage space?

Question

If I have a number of boxes of specified unit size (3 (1 x 1) boxes, 4 (1 x 2) boxes, and 2 (2 x 1) boxes, for instance), how can I figure out what the minimum total parameters are and what the best organization is to use the least possible space to place all the boxes?

Answer 1

I will just add this it is not efficient to find a relevant formula for something large scale as it will be more of an algorithm (trying methods and then changing your approach to make it a little better, doing that over and over would yield the best solution.

Blah blah blah... so how would it be done?

Draw a 2D area to scale and then cut out boxes to scale.  Put the rectangular cut outs in your 2D square you drew.  Move them around and try to pack them as tightly as possible.

I am an engineer and have used this method multiple times to figure out complex spacing issues within buildings.  A formula to do something like that?  Definitely not.  Especially with irregular shaped objects.

Answer 2

Presumably since you specify 1x2 and 2x1 separately,

rotating boxes is not permitted.

Also, presumably the overall shape is to be a rectangle.

In general, this is a very difficult problem which has been

explored extensively.  Look up "rectangle packing problem" or

"rectangular packing problem"

The numbers in your example are quite friendly,

so let's have a go with that one.

First figure out the total area.

In the example: 3 + 8 + 2 = 13.

Since all the dimensions will be integers,

that's a problem since 13 is prime, and

you can't do 13x1, since you need a height

of at least 2.

Let's try 7x2.

We'll start with the 1x2's

Each letter represents a box

A B C D ...

A B C D ...

Then the 2x1's

A B C D E E ...

A B C D F F ...

Then we just put down 1x1s (denoted as 1)

A B C D E E 1 1

A B C D F F 1 x

(x = open space)

So in this case we only wasted one square unit,

which is as well as we could have done.

If you want to get an idea of the difficulty of this problem,

consider something like this:

(3) 1x2  (1) 2x1 (2) 2x3  (4) 3x2 (3) 2x4  (1) 3x3

It's hard to know where to even begin with

something like that, let alone find a formula.

=