Container packing
Container packing is used in many scenarios, such as:
- packing storage boxes for moving
- filling shipping containers
- loading vehicles onto a ferry
The method of container packing that you are likely to be asked to do is one using first-fit algorithm.
First-fit algorithm
With first-fit algorithm you take the items you have to pack in any order.
As you come to each item you put it in the first container that can hold it. This might mean adding to a box that already has something in it. Or it might mean starting a new box.
First-fit is often used as it is a quick way to pack.
Example
Daryl is packing up his belongings, ready to move from home to his University accommodation.
He knows how much his belongings weigh but he is not sure how many boxes he will need to pack everything.
He has 8 items and the boxes he is using can safely hold \(5kg\) each.
| Item | A | B | C | D | E | F | G | H |
| Weight (\(kg\)) | \(1\) | \(3\) | \(2\) | \(1\) | \(4\) | \(3\) | \(1\) | \(2\) |
| Item |
|---|
| A |
| B |
| C |
| D |
| E |
| F |
| G |
| H |
| Weight (\(kg\)) |
|---|
| \(1\) |
| \(3\) |
| \(2\) |
| \(1\) |
| \(4\) |
| \(3\) |
| \(1\) |
| \(2\) |
To help Daryl to sort his belongings use the first-fit algorithm.
Starting with item \(A\), fit each item into the first available box. First available, means the first box that has enough room for the item, starting from box \(1\).
\(A\) and \(B\) will fit in box \(1\).
Item \(C\) is too heavy for Box \(1\). Daryl has to put it in Box \(2\).
Item \(D\) is light enough to go in Box \(1\). This fills the box to the maximum \(5kg\).
Item \(E\) cannot go in Box \(1\) as it is full. It is too heavy for Box \(2\) because Item \(C\) is in there already. So \(E\) is placed in Box \(3\).
Item \(F\) cannot go in Box \(1\) because it is full. But it can be held by Box \(2\).
Item \(G\) cannot fit in Boxes \(1\) and \(2\) as they are full. But it can go in Box \(3\).
Item \(H\) cannot go in Boxes \(1\), \(2\) or \(3\) as they are full. So it has to go in a new box, \(4\).
All Daryl's items are now packed. He needed \(4\) boxes in total.