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

Check out our iOS app: tons of questions to help you practice for your GCSE maths. Download free on the App Store (in-app purchases required).