First-Fit Bin Packing

1 An airline allows each passenger to carry a maximum of 25 kg in luggage. The four members of the Adams family have bags of the following weights (to the nearest kg ): The bags need to be grouped into bundles of 25 kg maximum so that each member of the family can carry a bundle of bags.

1. Use the first-fit method to group the bags into bundles of 25 kg maximum. Start with the bags belonging to Mr Adams, then those of Mrs Adams, followed by Sarah and finally Tim.
2. Use the first-fit decreasing method to group the same bags into bundles of 25 kg maximum.
3. Suggest a reason why the grouping of the bags in part (i) might be easier for the family to carry.

1

1. Use the first-fit method to pack the following weights in kg into boxes that can hold 8 kg each. $$\begin{array} { l l l l l l l } 2 & 4 & 3 & 3 & 2 & 5 & 4 \end{array}$$ Show clearly which weights are packed into which boxes.
2. Use the first-fit decreasing method to pack the same weights into boxes that can hold 8 kg each. You do not need to use an algorithm to sort the list into decreasing order.
3. First-fit decreasing is a quadratic order method. A computer takes 15 seconds to apply the first-fit decreasing method to a list of 1000 items; approximately how long will it take to apply the first-fit decreasing method to a list of 2000 items?

2 Two hikers each have a 25 litre rucksack to pack. The items to be packed have volumes of 14, 6, 11, 9 and 6 litres.

1. Apply the first fit algorithm to the items in the order given and comment on the outcome.
2. Write the five items in descending order of volume. Apply the first fit decreasing algorithm to find a packing for the rucksacks.
3. The hikers argue that the first fit decreasing algorithm does not produce a fair allocation of volumes to rucksacks. Produce a packing which gives a fairer allocation of volumes between the two rucksacks. Explain why the hikers might not want to use this packing.

1 Some jars need to be packed into small crates.
There are 17 small jars, 7 medium jars and 3 large jars to be packed.

• A medium jar takes up the same space as four small jars.
• A large jar takes up the same space as nine small jars.

Each crate can hold:

• at most 12 small jars,
• or at most 3 medium jars,
• or at most 1 large jar (and 3 small jars),
• or a mixture of jars of different sizes.
  1. One strategy is to fill as many crates as possible with small jars first, then continue using the medium jars and finally the large jars.

Show that this method will use seven crates. The jars can be packed using fewer than seven crates.

The jars are to be packed in the minimum number of crates possible.

• Describe how the jars can be packed in the minimum number of crates.
• Explain how you know that this is the minimum number of crates.

Some other numbers of the small, medium and large jars need to be packed into boxes.
The number of jars that a box can hold is the same as for a crate, except that

• a box cannot hold 3 medium jars.
• Describe a packing strategy that will minimise the number of boxes needed.

4. \(\begin{array} { l l l l l l l l l } 23 & 18 & 27 & 9 & 25 & 10 & 12 & 30 & 24 \end{array}\) The numbers in the list represent the weights, in kilograms, of nine suitcases. The suitcases are to be transported in containers that will each hold a maximum weight of 45 kilograms.

1. Calculate a lower bound for the number of containers that will be needed to transport the suitcases.
2. Use the first-fit bin packing algorithm to allocate the suitcases to the containers.
3. Using the list provided, carry out a bubble sort to produce a list of the weights in descending order. You need only give the state of the list after each complete pass.
4. Use the first-fit decreasing bin packing algorithm to allocate the suitcases to the containers.
5. Explain why it is not possible to transport the suitcases using fewer containers than the number used in (d).

1.

1. Use the first-fit bin packing algorithm to determine how the eleven numbers listed above can be packed into bins of size 14
2. The list of numbers is to be sorted into ascending order. Use a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.
3. Apply the first-fit decreasing bin packing algorithm to the sorted list to pack the numbers into bins of size 14
4. Explain why the number of bins used in part (c) is optimal.
5. Use the binary search algorithm to try to locate 3.0 in the list of numbers. Clearly indicate how you choose your pivots and which part of the list is rejected at each stage.

3. $$\begin{array} { l l l l l l l } 41 & 28 & 42 & 31 & 36 & 32 & 29 \end{array}$$ The numbers in the list represent the weights, in kilograms, of seven statues. They are to be transported in crates that will each hold a maximum weight of 60 kilograms.

1. Calculate a lower bound for the number of crates that will be needed to transport the statues.
2. Use the first-fit bin packing algorithm to allocate the statues to the crates.
3. Use the full bin algorithm to allocate the statues to the crates.
4. Explain why it is not possible to transport the statues using fewer crates than the number needed for part (c).

2.
0.6
0.2
0.4
0.5
0.7
0.1
0.9
0.3
1.5
1.6

1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 2.
   (3)
2. The list of numbers is to be sorted into descending order. Use a quick sort to obtain the sorted list. You must make your pivots clear.
3. Apply the first-fit decreasing bin packing algorithm to your ordered list to pack the numbers into bins of size 2 .
4. Determine whether your answer to (c) uses the minimum number of bins. You must justify your answer.

1. 0.2
1.7
1.9
1.2
1.4
1.5
2.1
3.0
3.2
3.3

1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 5 The list of numbers is now to be sorted into descending order.
2. Perform a quick sort on the original list to obtain the sorted list. You should show the result of each pass and identify your pivots clearly. For a list of \(n\) numbers, the quick sort algorithm has, on average, order \(n \log n\).
   Given that it takes 2.32 seconds to run the algorithm when \(n = 450\)
3. calculate approximately how long it will take, to the nearest tenth of a second, to run the algorithm when \(n = 11250\). You should make your method and working clear.

10 The numbers in the list above represent the lengths, in metres, of ten lengths of fabric. They are to be cut from rolls of fabric of length 60 m .

1. Calculate a lower bound for the number of rolls needed.
   (2)
2. Use the first-fit bin packing algorithm to determine how these ten lengths can be cut from rolls of length 60 m .
3. Use full bins to find an optimal solution that uses the minimum number of rolls.

12
10 The numbers in the list above represent the lengths, in metres, of ten lengths of fabric. They are to be cut from rolls of fabric of length 60 m .

1. Calculate a lower bound for the number of rolls needed.
   (2)
2. Use the first-fit bin packing algorithm to determine how these ten lengths can be cut from rolls of length 60 m .
3. Use full bins to find an optimal solution that uses the minimum number of rolls.

2.
32
45
17
23
38
28
16
9
12
10 The numbers in the list above represent the lengths, in metres, of ten lengths of fabric. They are to be cut from rolls of fabric of length 60 m .

1. Calculate a lower bound for the number of rolls needed.
2. Use the first-fit bin packing algorithm to determine how these ten lengths can be cut from rolls of length 60 m .
3. Use full bins to find an optimal solution that uses the minimum number of rolls.

17
23
38
28
16
9
12
10 The numbers in the list above represent the lengths, in metres, of ten lengths of fabric. They are to be cut from rolls of fabric of length 60 m .

1. Calculate a lower bound for the number of rolls needed.
2. Use the first-fit bin packing algorithm to determine how these ten lengths can be cut from rolls of length 60 m .
3. Use full bins to find an optimal solution that uses the minimum number of rolls.
   3. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{c1482d20-7bce-46cb-9ac8-c659ecad30de-3_755_624_283_283} \captionsetup{labelformat=empty} \caption{Figure 1}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{c1482d20-7bce-46cb-9ac8-c659ecad30de-3_750_620_285_1146} \captionsetup{labelformat=empty} \caption{Figure 2}
   \end{figure} Figure 1 shows the possible allocations of six workers, Charlotte (C), Eleanor (E), Harry (H), Matt (M), Rachel (R) and Simon (S) to six tasks, 1, 2, 3, 4, 5 and 6. Figure 2 shows an initial matching.
   1. List an alternating path, starting at H and ending at 4 . Use your path to find an improved matching. List your improved matching.
   2. Explain why it is not possible to find a complete matching. Simon (S) now has task 3 added to his possible allocation.
   3. Taking the improved matching found in (a) as the new initial matching, use the maximum matching algorithm to find a complete matching. List clearly the alternating path you use and your complete matching.
      (3)
      4. Miri
      Jessie
      Edward
      Katie
      Hegg
      Beth
      Louis
      Philip
      Natsuko
      Dylan
   4. Use the quick sort algorithm to sort the above list into alphabetical order.
      (5)
   5. Use the binary search algorithm to locate the name Louis.
      5. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{c1482d20-7bce-46cb-9ac8-c659ecad30de-5_940_1419_262_322} \captionsetup{labelformat=empty} \caption{Figure 3}
      \end{figure} [The total weight of the network is 625 m ]
      Figure 3 models a network of paths in a park. The number on each arc represents the length, in m , of that path.
      Rob needs to travel along each path to inspect the surface. He wants to minimise the length of his route.
   6. Use the route inspection algorithm to find the length of his route. State the arcs that should be repeated. You should make your method and working clear.
      (6) The surface on each path is to be renewed. A machine will be hired to do this task and driven along each path.
      The machine will be delivered to point G and will start from there, but it may be collected from any point once the task is complete.
   7. Given that each path must be traversed at least once, determine the finishing point so that the length of the route is minimised. Give a reason for your answer and state the length of your route.
      (3)
      6. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{c1482d20-7bce-46cb-9ac8-c659ecad30de-6_899_1493_262_285} \captionsetup{labelformat=empty} \caption{Figure 4}
      \end{figure} Figure 4 represents a network of roads. The number on each arc gives the length, in km , of that road.
   8. Use Dijkstra's algorithm to find the shortest distance from A to I. State your shortest route.
      (6)
   9. State the shortest distance from A to G .
      (1)
      7. Rose makes hanging baskets which she sells at her local market. She makes two types, large and small. Rose makes \(x\) large baskets and \(y\) small baskets. Each large basket costs \(\pounds 7\) to make and each small basket costs \(\pounds 5\) to make. Rose has \(\pounds 350\) she can spend on making the baskets.
   10. Write down an inequality, in terms of \(x\) and \(y\), to model this constraint.
       (2) Two further constraints are $$\begin{aligned} & y \leqslant 20 \text { and } \\ & y \leqslant 4 x \end{aligned}$$
   11. Use these two constraints to write down statements that describe the numbers of large and small baskets that Rose can make.
   12. On the grid provided, show these three constraints and \(x \geqslant 0 , y \geqslant 0\). Hence label the feasible region, R. Rose makes a profit of \(\pounds 2\) on each large basket and \(\pounds 3\) on each small basket. Rose wishes to maximise her profit, £P.
   13. Write down the objective function.
   14. Use your graph to determine the optimal numbers of large and small baskets Rose should make, and state the optimal profit.
       8. \begin{figure}[h]
       \includegraphics[alt={},max width=\textwidth]{c1482d20-7bce-46cb-9ac8-c659ecad30de-8_809_1541_283_262} \captionsetup{labelformat=empty} \caption{Figure 5}
       \end{figure} A construction project is modelled by the activity network shown in Figure 5. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, to complete the activity. Each activity requires one worker. The project is to be completed in the shortest possible time.
   15. Complete Diagram 2 in the answer book, showing the early and late event times.
   16. State the critical activities.
   17. Find the total float for activities M and H . You must make the numbers you use in your calculations clear.
   18. On the grid provided, draw a cascade (Gantt) chart for this project. An inspector visits the project at 1 pm on days 16 and 31 to check the progress of the work.
   19. Given that the project is on schedule, which activities must be happening on each of these days?

1. \(3.7 \quad 2.5\) \(5.4 \quad 1.9\) 2.7
3.2
3.1
2.7
4.2
2.0

1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 8.5 The first-fit bin packing algorithm is to be used to pack \(n\) numbers into bins. The number of comparisons is used to measure the order of the first-fit bin packing algorithm.
2. By considering the worst case, determine the order of the first-fit bin packing algorithm in terms of \(n\). You must make your method and working clear.

12.1 \quad 9.3 \quad 15.7 \quad 10.9 \quad 17.4 \quad 6.4 \quad 20.1 \quad 7.9 \quad 8.1 \quad 14.0

1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 33 \hfill [3]

The list is to be sorted into descending order.

1. 1. Starting at the left-hand end of the list, perform two passes through the list using a bubble sort. Write down the state of the list that results at the end of each pass.
   2. Write down the total number of comparisons and the total number of swaps performed during your two passes.
   \hfill [4]
2. Use a quick sort on the original list to obtain a fully sorted list in descending order. You must make your pivots clear. \hfill [4]
3. Use the first-fit decreasing bin packing algorithm to determine how the numbers listed can be packed into bins of size 33 \hfill [3]
4. Determine whether your answer to (d) uses the minimum number of bins. You must justify your answer. \hfill [1]

Five boxes weigh 5 kg, 2 kg, 4 kg, 3 kg and 8 kg. They are stacked, in the order given, with the first box at the top of the stack. The boxes are to be packed into bins that can each hold up to 10 kg.

1. Use the first-fit method to put the boxes into bins. Show clearly which boxes are packed in which bins. [2]
2. Use the first-fit decreasing method to put the boxes into bins. You do not need to use an algorithm for sorting. Show clearly which boxes are packed in which bins. [2]
3. Why might the first-fit decreasing method not be practical? [1]
4. Show that if the bins can only hold up to 8 kg each it is still possible to pack the boxes into three bins. [1]

The memory requirements, in KB, for eight computer files are given below. 43 \quad 172 \quad 536 \quad 17 \quad 314 \quad 462 \quad 220 \quad 231 The files are to be grouped into folders. No folder is to contain more than 1000 KB, so that the folders are small enough to transfer easily between machines.

1. Use the first-fit method to group the files into folders. [3]
2. Use the first-fit decreasing method to group the files into folders. [3]

First-fit decreasing is a quadratic order algorithm.

1. A computer takes 1.3 seconds to apply first-fit decreasing to a list of 500 numbers. Approximately how long will it take to apply first-fit decreasing to a list of 5000 numbers? [2]