The first fit rule is a method of allocating objects of various sizes into containers. Sometimes it is known as the bin packing algorithm.
There are several versions of the algorithm. The first version is the simple first fit method. Items are simply allocated to the first bin that they fit in as they are read from the list.
The second version is the first fit descending algorithm. The items are sorted in descending order first before reading them from the list and being placed in a bin. Generally, this second process provides a better fit than the algorithm without the sort.
In either case, select each item from the list and, for each item, work through the bins in turn to see which bin it fits into. The bins fill up as items are added, so keep track of the remaining space for each bin.
A distribution service uses crates for its products. Each crate can take 50 items. There are a number of consignments to go out, with each consignment containing 5 or more items.
The number of items in each consignment are as follow:
42, 7, 11, 19, 32, 8, 34, 17, 24, 14, 8, 5, 9, 12, 22, 26, 5
Using the first fit rule, what is the minimum number of crates needed to transport all of the consignments?
Lay out a table as shown below. Taking each number in turn, work through the bins to see if the number will fit into the remaining space eg
42 goes into Bin 1 (8 remaining spaces in Bin 1)
7 goes into Bin 1 (1 space remaining in Bin 1)
11 cannot go into Bin 1, so goes into Bin 2 (39 spaces left in Bin 2)
19 cannot go into Bin 1, but can go into Bin 2 (20 spaces left in Bin 2)
32 cannot go into Bin 1 or Bin, so goes into Bin 3 (18 spaces left in bin 3)
8 cannot go into Bin 1, but can go into Bin 2 (12 spaces left in Bin 2) etc
| Bin 1 | 42, 7 | 1 space left |
| Bin 2 | 11, 19, 8, 8 | 4 spaces left |
| Bin 3 | 32, 17 | 1 space left |
| Bin 4 | 34, 14 | 2 spaces left |
| Bin 5 | 24, 5, 9, 12 | no space left |
| Bin 6 | 22, 26 | 2 spaces left |
| Bin 7 | 5 | 45 spaces left |
Answer: 7
Use the First Fit Descending rule on the example above. How many bins are now required?
Before allocating the numbers into the bins, sort them in descending order first:
42 34 32 26 24 22 19 17 14 12 11 9 8 8 7 5 5
and repeat the process of allocating the consignments to the bins:
| Bin 1 | 42, 8 | no spaces left |
| Bin 2 | 34, 14 | 2 spaces left |
| Bin 3 | 32, 17 | 1 space left |
| Bin 4 | 26, 24 | no spaces left |
| Bin 5 | 22, 19, 9 | no space left |
| Bin 6 | 12, 11, 8, 7, 5, 5 | 2 spaces left |
Answer: 6