Molly Roberts

Ah, going on holiday. A few days away to relax and have fun, far away from the trials and tribulations of everyday life. If only you didn’t have to worry about how on earth you were going to pack all your bags, fit everything in the car, and actually get to where you’re supposed to be going.

Well, my friends, you needn’t stress any longer. In this series of articles, I will be discussing various algorithms which will make your holiday preparations more efficient and logical than ever before. Never again will you sit on top of your bag desperately trying to convince yourself that those extra books you won’t actually read are GOING TO FIT! Never again will you come to pack the car, only to find your bags in a disorganised heap by the front door, resulting in you throwing them haphazardly into the boot and pretending you don’t know they’ll all fall out again the minute you open it. Never again will you shout and swear at your sat nav because you have no idea how it decided this was the quickest route when you’ve been sat in traffic for at least five hours. Welcome to paradise.

First, I’m going to talk about a few algorithms you could use to pack your bags without ending up wanting to pull your hair out.

We begin by assigning values to each item we want to pack, for example by volume. Then for the sake of this article, we are going to make several assumptions in order to simplify the theory a little:

1. All the bags have the same volume of 100 litres, and that they have been ordered
2. The capacity of the bags is only limited by volume i.e. we discount any issues such as shape, mass, or physical size of the items
3. All of the items have known volume less than or equal to 100 litres, and they too have been ordered in some way

Of course, this is less practical in real life for a multitude of reasons: items could be awkward shapes, bags are probably not all the same size, and chances are you don’t know the exact volume of any of the items you want to pack – apart from your shampoo. However, for now, it is what we are going to assume in order to learn the algorithms.

Next Fit

The first algorithm we will discuss is the next fit algorithm. In order to obey this algorithm for your packing, you must carry out the following steps:

Step 1: Pick up the first item in the pile, and put it into the first bag.

Step 2: Pick up the next item in the pile. If it fits into the first bag, place the item in the first bag and then repeat this step. Otherwise, close the first bag and place the item in the second bag.

Step 3: Pick up the next item in the pile. If it fits into the second bag, place the item in the second bag and then repeat this step. Otherwise, close the second bag and place the item in the third bag.

And so on and so forth. Essentially, you use a bag until you encounter an item which will not fit into it, and then you close that bag and move onto the next one. If you have closed all your bags, you stop carrying out the algorithm.

Now with a little bit of thought, you may realise this seems rather silly. What if you have closed all your bags and still have items left? Let’s try an example to see how it works in practice.

Suppose we have two bags each with a capacity of 100 litres, and five items of ordered capacities 40 litres, 80 litres, 10 litres, 60 litres and 10 litres. Following the ‘Next Fit’ algorithm the first bag will end up with the 40 litre item, and is then closed, since the 80 litre item is next and will not fit. The second bag will then take the 80 litre item and one of the 10 litre items, and is then closed. The 60 litre item and the other 10 litre item will remain unpacked, as we have closed both bags.

The algorithm would stop here, leaving the last 2 items unpacked, but of course in real life you would just open one of the bags and fit the other items in as best you could. Especially if it was something incredibly important, like a set of your pants. So, perhaps we should consider a better algorithm?

First Fit

The ‘First Fit’ algorithm, as you will see, feels intuitively smarter than next fit. In fact, in all likelihood, you often subconsciously use some variation of this algorithm when you are packing your bags anyway. Here are the steps:

Step 1: Pick up the first item in the pile, and put it into the first bag.

Step 2: If there are no more items, stop. Otherwise, pick up the next item in the pile, and put it into the first bag in which it fits, if there is such a bag, and then repeat this step. Otherwise, do not pack this item, and repeat step 2.

This algorithm, unlike the previous one, does not involve closing any bags. All the bags are kept open until you’ve finished packing. Like before, let’s try it with an example to see how it works. Using the same bags and ordered list of items as before, we will end up with the 40 litre and two 10 litre items in the first bag, the 80 litre item in the second bag, and the 60 litre item being left unpacked:

As we can see, this is marginally better than the result from using First Fit – we have managed to pack an extra item after all! But hang on a minute, this still doesn’t seem like a very smart way of packing the items. Looking at the numbers involved in the problem and applying some simple logic, we see that it is indeed possible to fit everything into the two bags. Perhaps it’s time to bring out the big guns…

Best Fit

How does the saying go? Best by name, best by nature? Well, here’s to hoping this algorithm is an improvement on the other two! It goes something like this:

Step 1: Put the first item into the first bag.

Step 2: If there are no more items, stop. Otherwise, put the next item into the next bag into which it fits, which also has the smallest amount of space remaining (if there is such a bag), and repeat step 2. Otherwise, do not pack this item, and repeat step 2.

Now, this algorithm is very similar to First Fit, with the exception that instead of putting items into the first bag they fit into, the place where they are packed is more carefully considered. By putting the item into the bag with the least amount of space left, we are trying to use up all the available smaller spaces before cramming larger spaces full of multiple small items when they could instead be reserved for bigger items.

This algorithm gives a much better, and in fact optimal, solution to the example above. After placing the 40 and 80 litre items into separate bags, instead of placing the 10 litre item in the first bag as in First Fit, it goes into the second, as it has a smaller amount of space remaining. Now, we end up having space for the 60 litre item in the first bag, and the two 10 litre items fit perfectly into the remaining space in bag two. All items are packed, and all bags are full. Success!

Now, as you may have guessed, all of these algorithms would work differently on our set of items if they were placed in a different order. For example, if we place them instead in the order 40, 10, 60, 80, 10, then Next Fit leaves 80 and one of the 10s unpacked, and both First Fit and Best Fit leave the 80 unpacked (although with different combinations within the bags). So as you can see, Best Fit does not always give a better solution than First Fit, and likewise First Fit will not always give a better solution than Next Fit.

These algorithms are called heuristic algorithms, which means they are designed to solve a problem quickly and without necessarily providing the optimum (best) solution. In other words, they provide a reliable set of guidelines for doing your packing so that you know where to start, but they might not always give you a better solution than you can come up with yourself if you spend a little bit of time thinking about it. (Although who wants to do that when they’re just about to go on holiday!)

Why don’t you have a go at carrying out each of the algorithms on a set of 3 bags each with volume 100 litres, together with ordered items of volumes 40, 30, 60, 70, 20, 10, and 70 litres. Which one gives the best result? And can you come up with a better solution yourself?

[Scroll down for the solution!]

.

.

.

.

.

.

.

.

.

.

.

.

Answers

Next Fit: Bag 1 has 30 and 40, bag 2 has 60, bag 3 has 70, 20, and 10, and the second 70 is unpacked.

First Fit: Bag 1 has 40, 30, 20, and 10, bag 2 has 60, bag 3 has 70, and the second 70 is unpacked.

Best Fit: The same as first fit.

Optimal: Bag 1 has 40 and 60, bag 2 has 70 and 30, and bag 3 has 70, 20, and 10 (or some permutation of this).

If you enjoyed this article, and want to check out the next stages of the mathematical holiday, you can find parts 2 and 3 at the links below:

Mathematical Holiday Part 2 – Sorting The Luggage

Mathematical Holiday Part 3 – Using The Sat Nav