7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin

3 The famous fictional detective Agatha Parrot has been called in to investigate the theft of some jewels. Each thief is known to have taken just one item of jewellery. Agatha has invented a scoring system based on motive, opportunity and past experience. The table shows the score for each of four suspects with each of three items of jewellery. The higher the score the more likely the suspect is to have stolen that item of jewellery. Suspect

1. Assuming that three of these four suspects are the thieves, find who is most likely to have stolen each item of jewellery for the total score to be maximised. State how each table of working was calculated. Write down the two possible solutions for who should be suspected of stealing each item of jewellery and who should be thought to be innocent. Further evidence shows that the butler stole the sapphire bracelet.
2. Using this additional information, find out which suspect should be thought to be innocent. Explain your reasoning.

3 Agatha Parrot is in her garden and overhears her neighbours talking about four new people who have moved into her village. Each of the new people has a different job, and Agatha's neighbours are guessing who has which job. Using the information she has overheard, Agatha counts how many times she heard it guessed that each person has each job. Agatha wants to find the allocation of people to jobs that maximises the total number of correct guesses. She intends to use the Hungarian algorithm to do this. She starts by subtracting each value in the table from 10.

1. Write down the table which Agatha gets after she has subtracted each value from 10. Explain why she did a subtraction.
2. Apply the Hungarian algorithm, reducing rows first, to find which job Agatha concludes each person has. State how each table of working was calculated from the previous one. Agatha later meets Liz Lomax and is surprised to find out that she is the radiographer.
3. Using this additional information, but without formally using the Hungarian algorithm, find which job Agatha should now conclude each person has. Explain how you know that there is no better solution in which Liz is the radiographer.

1 D aniel needs to clean four houses but only has one day in which to do it. He estimates that each house will take one day and so he has asked three professional cleaning companies to give him a quotation for cleaning each house. He intends to hire the three companies to clean one house each and he will clean the fourth house himself. The table below shows the quotations that Daniel was given by the three companies.

1. Copy the table and add a dummy row to represent D aniel.
2. A pply the Hungarian algorithm, reducing rows first, to find a minimum cost matching. You must show your working and say how each matrix was formed.
3. Which house should Daniel ask each company to clean? Find the total cost of hiring the three companies.

2 Granny is on holiday in Amsterdam and has bought some postcards. She wants to send one card to each member of her family. She has given each card a score to show how suitable it is for each family member. The higher the score the more suitable the card is. \begin{table}[h] \end{table} Granny adds two dummy columns, \(G\) and \(H\), both with score 0 for each postcard. She then modifies the resulting table so that she can use the Hungarian algorithm to find the matching for which the total score is maximised.

1. Explain why the dummy columns were needed, why they should not have positive scores and how the resulting table was modified.
2. Show that, after reducing rows and columns, Granny gets this reduced cost matrix.

   	A	B	\(C\)	D	\(E\)	\(F\)	\(G\)	\(H\)
   \(P\)	4	2	4	0	6	2	2	2
   \(Q\)	2	0	2	0	2	1	1	1
   \(R\)	2	1	2	2	2	0	4	4
   \(S\)	2	0	2	2	6	2	2	2
   \(T\)	4	5	4	1	5	0	1	1
   \(U\)	1	0	0	0	1	1	0	0
   \(V\)	0	2	0	1	0	2	3	3
   \(W\)	2	0	1	2	1	1	2	2

3. Complete the application of the Hungarian algorithm, showing your working clearly. Write down which family member is sent each postcard, and which postcards are not used, to maximise the score.

2 The cadets in Blue Team have been set a task that requires them to get inside a guarded building. Every two hours one of them will attempt to get inside the building. Each cadet will have one attempt. The table shows a score for each cadet attempting to get inside the building at each time. The higher the score the more likely the cadet is to succeed. Time

1. Explain how to modify the table so that the Hungarian algorithm can be used to find the matching for which the total score is maximised.
2. Show that, after modifying the table and then reducing rows and then columns, the reduced cost matrix becomes:

   	2330	0130	0330	0530	0730
   \(G\)	0	6	0	3	4
   \(H\)	0	5	1	5	4
   \(I\)	0	4	0	3	2
   \(J\)	0	3	0	2	2
   \(K\)	0	0	0	0	0

3. Complete the application of the Hungarian algorithm, stating how each table was formed. Write down the order in which the cadets should attempt to get into the building to maximise the total score. If the cadets use this solution, which one is least likely to succeed?

7. Mrs. Hartley organises the tennis fixtures for her school. On one day she has to send a team of 10 players to a match against school \(A\) and a team of 6 players to a match against school \(B\). She has to select the two teams from a squad that includes 7 players who live in village \(C\), 5 players who live in village \(D\) and 8 players who live in village \(E\). Having a small budget, Mrs. Hartley wishes to minimise the total amount spent on travel. The table below shows the cost, in pounds, for one player to travel from each village to each of the schools they are competing against.

1. Use the north-west corner rule to find an initial solution to this problem.
2. Obtain improvement indices for this initial solution.
3. Use the stepping-stone method to obtain an optimal solution and state the pattern of transportation that this represents. \section*{Please hand this sheet in for marking}

   Stage	State	Action
   \multirow[t]{2}{*}{1}	G	GI
   	H	HI
   \multirow[t]{3}{*}{2}	D	DG DH
   	E	EG \(E H\)
   	F	FG FH
   \multirow[t]{3}{*}{3}	A	AD \(A E\) \(A F\)
   	B	BD BE \(B F\)
   	C	CD CE CF
   4	Home	Home-A Home-B Home-C

   \section*{Please hand this sheet in for marking}
   1. \includegraphics[max width=\textwidth, alt={}, center]{4e50371b-0c1c-4b4e-b21d-60858ae160df-8_662_1025_529_440}
   2. Sheet for answering question 6 (cont.)

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.

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

7 Six items need to be packed into bins. Each bin has size \(k\), where \(k\) is an integer. The sizes of the items are \(\begin{array} { l l l l l l } 8 & 5 & 4 & 7 & 3 & 3 \end{array}\)

1. Show a way to pack the items into two bins of size \(k = 18\).
2. If exactly three bins are needed, determine the possible values of \(k\).
3. Use the first-fit method to pack the items into bins of size 12.
4. Explain why, in general, the first-fit algorithm does not necessarily find the most efficient solution to a packing problem. A possible way to calculate the run-time of the first-fit method is to count for each item the number of bins, excluding full bins, that are considered before the bin where each item is packed. The total count for all packed items is then used to calculate the run-time of the method.
5. Determine the total count for the packing used in part (c). A student says that when \(k = 13\) the total count is 0 because the first bin fills up before the second bin is considered.
6. Explain why the student's argument is not correct.
7. Determine the least possible value of \(k\) for which the total count is 0 . \section*{END OF QUESTION PAPER}

2 Jameela needs to store ten packages in boxes. She has a list showing the size of each package. The boxes are all the same size and Jameela can use up to six of these boxes to store all the packages.

1. Which of the following is a question that Jameela could ask which leads to a construction problem? Justify your choice.
   The total volume of the packages is \(1 \mathrm {~m} ^ { 3 }\). The volume of each of the six boxes is \(0.25 \mathrm {~m} ^ { 3 }\).
2. Explain why a solution to the problem of storing all the packages in six boxes may not exist. The volume of each package is given below.

   Package	A	B	C	D	E	F	G	H	I	J
   Volume \(\left( \mathrm { m } ^ { 3 } \right)\)	0.20	0.05	0.15	0.25	0.04	0.03	0.02	0.02	0.12	0.12

3. By considering the five largest packages (A, C, D, I and J) first, explain what happens if Jameela tries to pack the 10 packages using only four boxes. You may now assume that the packages will always fit in the boxes if there is enough volume.
4. Use first-fit to find a way of storing the packages in the boxes. Show the letters of the packages in each box, in the order that they are packed into that box. The order of the packages within a box does not matter and the order of the boxes does not matter. So, for example, having A and E in box 1 is the same as having E and A in box 2 , but different from having A in one box and E in a different box.
5. Suppose that packages A and B are not in the same box. In this case the following are true:
   Use the inclusion-exclusion principle to determine how many of the 8 ways include neither package F nor package G.

6 The following masses, in kg, are to be packed into bins. $$\begin{array} { l l l l l l l l l l } 8 & 5 & 9 & 7 & 7 & 9 & 1 & 3 & 3 & 8 \end{array}$$

1. Chloe says that first-fit decreasing gives a packing that requires 4 bins, but first-fit only requires 3 bins. Find the maximum capacity of the bins. First-fit requires one pass through the list and the time taken may be regarded as being proportional to the length of the list. Suppose that shuttle sort was used to sort the list into decreasing order.
2. What can be deduced, in this case, about the order of the time complexity, \(\mathrm { T } ( n )\), for first-fit decreasing?

1 Sam is packing for a holiday. The table shows the mass of each item to be packed. Sam's bags can each carry 10 kg , but no more.

1. Use first-fit to show a possible packing that Sam could use. Indicate the items by using the letters \(A , B , \ldots\) rather than their masses. The total mass of the 8 items is 39.5 kg . Sam says that this means they can be packed using just 4 bags.
2. Explain why Sam cannot pack the items using just 4 bags. Sam is only allowed to take 4 bags. Each item is given a value out of 20 representing how important it is to Sam.

   Item	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)	\(G\)	\(H\)
   Mass (kg)	3	4	3.5	2.5	6	7.5	8	5
   Value	6	10	12	10	16	12	20	14

3. Sam wishes to pack items with a large total value.

3. $$\begin{array} { l l l l l l l l l l } 1.1 & 0.7 & 1.9 & 0.9 & 2.1 & 0.2 & 2.3 & 0.4 & 0.5 & 1.7 \end{array}$$

1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 3 The list is to be sorted into descending order.
2. 1. Starting at the left-hand end of the list, perform one pass through the list using a bubble sort. Write down the list that results at the end of your first pass.
   2. Write down the number of comparisons and the number of swaps performed during your first pass. After a second pass using this bubble sort, the updated list is $$\begin{array} { l l l l l l l l l l } 1.9 & 1.1 & 2.1 & 0.9 & 2.3 & 0.7 & 0.5 & 1.7 & 0.4 & 0.2 \end{array}$$
3. Use a quick sort on this updated list to obtain the fully sorted list. You must make your pivots clear.
4. Apply the first-fit decreasing bin packing algorithm to your fully sorted list to pack the numbers into bins of size 3

3.
6.4
7.9
8.1
12.19 .3
14.0
15.7
17.4
20.1

1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 33 The list is to be sorted into descending order.
2. 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.
3. Use a quick sort on the original list to obtain a fully sorted list in descending order. You must make your pivots clear.
4. Use the first-fit decreasing bin packing algorithm to determine how the numbers listed can be packed into bins of size 33
5. Determine whether your answer to (d) uses the minimum number of bins. You must justify your answer.

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).

6. $$\begin{array} { l l l l l l l l l l } 30 & 11 & 21 & 53 & 50 & 39 & 16 & 4 & 60 & 43 \end{array}$$ The numbers in the list above represent the lengths, in cm, of some pieces of electrical wire. The wire is sold in one metre lengths.

1. Use the first-fit bin packing algorithm to determine how these pieces could be cut from one metre lengths. You should ignore wastage due to cutting. The list of numbers above is to be sorted into ascending order.
   Starting at the left-hand end of the list, after three passes of the bubble sort, the list is $$\begin{array} { l l l l l l l l l l } 11 & 21 & 30 & 16 & 4 & 39 & 43 & 50 & 53 & 60 \end{array}$$
2. 1. Write down the list that results at the end of the fourth pass.
   2. Write down the number of comparisons and swaps performed during the fourth pass. The original list of numbers is now to be sorted into descending order.
3. Perform a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.
4. Use the first-fit decreasing bin packing algorithm to determine how these pieces could be cut from one metre lengths. You should ignore wastage due to cutting.

4. $$\begin{array} { l l l l l l l l l l l } 180 & 80 & 250 & 115 & 100 & 230 & 150 & 95 & 105 & 90 & 390 \end{array}$$ The numbers in the list above represent the weights, in kilograms, of 11 boxes. John must transport all the boxes using his van. You may assume the van has sufficient space for any combination of boxes. Each van load of boxes must weigh at most 475 kg .

1. Calculate a lower bound for the number of van loads needed to transport all 11 boxes.
2. Use the first-fit bin packing algorithm to show how the boxes could be put into van loads. State the number of van loads needed according to this solution.
3. Carry out a quick sort on the numbers in the list given above to produce a list of the weights in descending order. You should show the result of each pass and identify your pivots clearly.
4. Use the first-fit decreasing bin packing algorithm on your ordered list to show how the boxes could be put into van loads. State the number of van loads needed according to this solution. Due to volume restrictions, the van cannot transport more than three boxes at any one time.
5. Show how the boxes could now be put into the minimum number of van loads.

4. $$\begin{array} { l l l l l l l l l l } 35 & 17 & 10 & 7 & 28 & 23 & 41 & 15 & 20 & 29 \end{array}$$

1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 60
2. The list of numbers is to be sorted into descending order. Use a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.
3. Use the first-fit decreasing bin packing algorithm on your ordered list to pack the numbers into bins of size 60 The ten distinct numbers below are to be sorted into descending order. $$\begin{array} { l l l l l l l l l l } 20 & 24 & 17 & 26 & 8 & 15 & x & y & 19 & 12 \end{array}$$ A bubble sort, starting at the left-hand end of the list, is to be used to obtain the sorted list.
   After the second complete pass the list is $$\begin{array} { l l l l l l l l l l } 24 & 26 & 20 & 17 & 15 & y & 19 & 12 & x & 8 \end{array}$$
4. Find the constraints on the values of \(x\) and \(y\).

3. \(\quad \begin{array} { l l l l l l l l l l } 2.6 & 0.8 & 2.1 & 1.2 & 0.9 & 1.7 & 2.3 & 0.3 & 1.8 & 2.7 \end{array}\)

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 is to be sorted into descending order.
2. 1. Starting at the left-hand end of the above list, perform two passes through the list using a bubble sort. Write down the lists that result at the end of the first pass and the second pass.
   2. Write down, in the table in the answer book, the number of comparisons and the number of swaps performed during each of these two passes. After a third pass using this bubble sort, the updated list is $$\begin{array} { l l l l l l l l l l } 2.6 & 2.1 & 1.7 & 2.3 & 1.2 & 1.8 & 2.7 & 0.9 & 0.8 & 0.3 \end{array}$$
3. Use a quick sort on this updated list to obtain the fully sorted list. You must make your pivots clear.
4. Apply the first-fit decreasing bin packing algorithm to the fully sorted list to pack the numbers into bins of size 5

3. \(\begin{array} { l l l l l l l l l l l } 1.8 & 1.4 & 2.6 & 1.6 & 2.8 & 0.9 & 3.1 & 0.8 & 1.2 & 2.4 & 0.6 \end{array}\) \section*{Question 3 continued} \section*{Question 3 continued} \section*{Question 3 continued}

6. The twelve numbers in the list below are to be packed into bins of size \(n\), where \(n\) is a positive integer. When the first-fit bin packing algorithm is applied to the list, the following allocation is obtained. Bin 1: 28315
Bin 2: 25161811
Bin 3: 352215
Bin 4: 2713

1. Based on the packing shown above, determine the possible values of \(n\). You must give reasons for your answer.
2. The original list of twelve 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. When the first-fit decreasing bin packing algorithm is applied to the list, the following allocation is obtained. Bin 1: 35315
   Bin 2: 282716
   Bin 3: 252218
   Bin 4: 151311
3. Determine the value of \(n\). You must give a reason for your answer.

2. A list of \(n\) numbers needs to be sorted into descending order starting at the left-hand end of the list.

1. Describe how to carry out the first pass of a bubble sort on the numbers in the list.
2. 1. State which number in the list is guaranteed to be in the correct final position after the first pass.
   2. Write down the maximum number of passes required to sort a list of \(n\) numbers.
3. The numbers below are to be sorted into descending order. Use a bubble sort, starting at the left-hand end of the list, to obtain the sorted list. You need only give the state of the list after each pass. $$\begin{array} { l l l l l l l l l } 11 & 9 & 4 & 13 & 5 & 1 & 7 & 12 & 8 \end{array}$$
4. Apply the first-fit decreasing bin packing algorithm to your ordered list to pack the numbers into bins of size 21

1. $$\begin{array} { l l l l l l l l l } 4.2 & 1.8 & 3.1 & 1.3 & 4.0 & 4.1 & 3.7 & 2.3 & 2.7 \end{array}$$

1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 7.8
2. Determine whether the number of bins used in (a) is optimal. Give a reason for your answer.
3. 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. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{049de386-42a9-4f16-8be3-9324382e4988-02_586_1356_906_358} \captionsetup{labelformat=empty} \caption{Figure 1}
   \end{figure}
4. Use Kruskal's algorithm to find a minimum spanning tree for the network in Figure 1. You must show clearly the order in which you consider the arcs. For each arc, state whether or not you are including it in your minimum spanning tree. A new spanning tree is required which includes the arcs AB and DE , and which has the lowest possible total weight.
5. Explain why Prim's algorithm could not be used to complete the tree.

1. $$\begin{array} { l l l l l l l l l l l } 2.5 & 0.9 & 3.1 & 1.4 & 1.5 & 2.0 & 1.9 & 1.2 & 0.3 & 0.4 & 3.9 \end{array}$$ The numbers in the list are the lengths, in metres, of eleven pieces of wood. They are to be cut from planks of wood of length 5 metres. You should ignore wastage due to cutting.

1. Calculate a lower bound for the number of planks needed. You must make your method clear.
2. Use the first-fit bin packing algorithm to determine how these pieces could be cut from 5 metre planks.
3. Carry out a quick sort to produce a list of the lengths in descending order. You should show the result of each pass and identify your pivots clearly.
4. Use the first-fit decreasing bin packing algorithm to determine how these pieces could be cut from 5 metre planks.

3. Pupils from ten schools are visiting a museum on the same day. The museum needs to allocate each school to a tour group. The maximum size of each tour group is 42 pupils. A group may include pupils from more than one school. Pupils from each school must be kept in the same tour group. The numbers of pupils visiting from each school are given below. $$\begin{array} { l l l l l l l l l l } 8 & 17 & 9 & 14 & 18 & 12 & 22 & 10 & 15 & 7 \end{array}$$

1. Calculate a lower bound for the number of tour groups required. You must make your method clear.
2. Using the above list, apply the first-fit bin packing algorithm to allocate the pupils visiting from each school to tour groups. The above list of numbers is to be sorted into descending order.
3. Perform a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly.
4. Using your sorted list from (c), apply the first-fit decreasing bin packing algorithm to obtain a second allocation of pupils to tour groups. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{aef6a6dd-76ec-47f7-b8c9-449006da29d3-04_712_1141_1363_463} \captionsetup{labelformat=empty} \caption{Figure 2}
   \end{figure} [The total weight of the network is 227.2]
   Figure 2 represents the corridors in the museum. The number on each arc is the length, in metres, of the corresponding corridor. Sally is a tour guide in the museum and she must travel along each corridor at least once during each tour. Sally wishes to minimise the length of her route. She must start and finish at the museum's entrance at A .
5. Use an appropriate algorithm to find the corridors that Sally will need to traverse twice. You should make your method and working clear.
6. Write down a possible shortest route, giving its length. Sally is now allowed to start at H and finish her route at a different vertex. A route of minimum length that includes each corridor at least once needs to be found.
7. State the finishing vertex of Sally's new route and calculate the difference in length between this new route and the route found in (f).

2.

1. 1. Describe how to carry out the first pass of a bubble sort when it is used to sort a list of \(n\) numbers into ascending order.
   2. Write down the circumstances under which a bubble sort stops. A bubble sort, starting at the left-hand end of the list, is used to sort a list of ten numbers into ascending order. After a number of passes the list reads
      0.9
      0.5
      0.7
      1.2
      1.5
      1.4
      1.1
      1.7
      2.2
      3.2
2. Determine the maximum number of passes that could have taken place on this list. You must give a reason for your answer.
3. Complete the bubble sort to produce a list of the numbers in ascending order. You only need to give the state of the list after each complete pass.
4. Use the first-fit decreasing bin packing algorithm to determine how the ten numbers listed above can be packed into bins of size 4