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

1. \(\begin{array} { l l l l l l l l l l l l l } 16 & 23 & 18 & 9 & 4 & 20 & 35 & 5 & 17 & 13 & 6 & 11 \end{array}\) The numbers in the list represent the weights, in kilograms, of twelve parcels. The parcels are to be transported in containers that will each hold a maximum weight of 45 kg .

1. Calculate a lower bound for the number of containers needed. You must make your method clear.
2. Use the first-fit bin packing algorithm to allocate the parcels to the containers.
3. Carry out a bubble sort, starting at the left-hand end of the list, to produce a list of the weights in descending order. You should only give the state of the list after each pass.
4. Use the first-fit decreasing bin packing algorithm to allocate the parcels to the containers.

1. \(\quad \begin{array} { l l l l l l l l l l } 175 & 135 & 210 & 105 & 100 & 150 & 60 & 20 & 70 & 125 \end{array}\)

The numbers in the list above represent the weights, in kilograms, of ten crates. The crates are to be transported in trucks that can each hold a maximum total crate weight of 300 kg .

1. Calculate a lower bound for the number of trucks that will be needed to transport the crates.
2. 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 pass.
3. Use the first-fit decreasing bin packing algorithm to allocate the crates to the trucks.
   

2. A list of eleven numbers is to be sorted into descending order. After one pass, the quick sort algorithm produces the following list $$\begin{array} { l l l l l l l l l l l } 17 & 33 & 14 & 25 & 23 & 28 & 21 & 13 & 9 & 6 & 10 \end{array}$$

1. State, with a reason, which number was used as a pivot for the first pass.
2. Starting at the left-hand end of the above list, obtain the fully sorted list using a bubble sort. You need to write down only the list that results at the end of each pass.
3. Apply the first-fit decreasing bin packing algorithm to the fully sorted list to pack the numbers into bins of size 85

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.

7. The numbers listed below are to be packed into bins of size \(n\), where \(n\) is a positive integer.
14
20
23
17
15
22
19
25

20
23
17
15
22
19
25
13
28
32 A lower bound for the number of bins required is 4

1. Determine the range of possible values of \(n\). You must make your method clear.
   (3)
2. Carry out a quick sort to produce a list of the numbers in descending order. You should show the result of each pass and identify your pivots clearly.
   (4) When the first-fit bin packing algorithm is applied to the original list of numbers, the following allocation is achieved. \end{table}
   \includegraphics[max width=\textwidth, alt={}]{d409aaae-811d-4eca-b118-efc927885f97-14_1193_1586_1270_185}
   Shortest path from A to J: \(\_\_\_\_\) Length of shortest path from A to J: \(\_\_\_\_\) \section*{2. \(\_\_\_\_\)} \section*{3.}

   	A	B	C	D	E	F	G	H
   A	-	36	38	40	23	39	38	35
   B	36	-	35	36	35	34	41	38
   C	38	35	-	39	25	32	40	40
   D	40	36	39	-	37	37	26	33
   E	23	35	25	37	-	42	24	43
   F	39	34	32	37	42	-	45	38
   G	38	41	40	26	24	45	-	40
   H	35	38	40	33	43	38	40	-

   	A	B	C	D	E	F	G	H
   A	-	36	38	40	23	39	38	35
   B	36	-	35	36	35	34	41	38
   C	38	35	-	39	25	32	40	40
   D	40	36	39	-	37	37	26	33
   E	23	35	25	37	-	42	24	43
   F	39	34	32	37	42	-	45	38
   G	38	41	40	26	24	45	-	40
   H	35	38	40	33	43	38	40	-

   	A	B	C	D	E	F	G	H
   A	-	36	38	40	23	39	38	35
   B	36	-	35	36	35	34	41	38
   C	38	35	-	39	25	32	40	40
   D	40	36	39	-	37	37	26	33
   E	23	35	25	37	-	42	24	43
   F	39	34	32	37	42	-	45	38
   G	38	41	40	26	24	45	-	40
   H	35	38	40	33	43	38	40	-

   	A	B	C	D	E	F	G	H
   A	-	36	38	40	23	39	38	35
   B	36	-	35	36	35	34	41	38
   C	38	35	-	39	25	32	40	40
   D	40	36	39	-	37	37	26	33
   E	23	35	25	37	-	42	24	43
   F	39	34	32	37	42	-	45	38
   G	38	41	40	26	24	45	-	40
   H	35	38	40	33	43	38	40	-

   4. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{d409aaae-811d-4eca-b118-efc927885f97-22_755_1157_246_404} \captionsetup{labelformat=empty} \caption{Figure 2}
   \end{figure}

   1. Activity	Immediately preceding activities
      A
      B
      C
      D
      E

      Activity	Immediately preceding activities
      F
      G
      H
      I
      J

      Activity	Immediately preceding activities
      K
      L
      M

      $$v = \ldots \quad x = \ldots \quad y = \ldots$$ \includegraphics[max width=\textwidth, alt={}, center]{d409aaae-811d-4eca-b118-efc927885f97-23_2255_56_315_37}
      \includegraphics[max width=\textwidth, alt={}]{d409aaae-811d-4eca-b118-efc927885f97-23_1153_1338_303_310}
      \section*{Grid 2} 5. \begin{figure}[h]
      \includegraphics[alt={},max width=\textwidth]{d409aaae-811d-4eca-b118-efc927885f97-24_591_1433_255_260} \captionsetup{labelformat=empty} \caption{Figure 3
      [0pt] [The total weight of the network is 166]}
      \end{figure} 6.
      \includegraphics[max width=\textwidth, alt={}]{d409aaae-811d-4eca-b118-efc927885f97-26_1287_1645_301_162}
      \section*{Diagram 1} 7. \(\begin{array} { l l l l l l l l l l l } 14 & 20 & 23 & 17 & 15 & 22 & 19 & 25 & 13 & 28 & 32 \end{array}\)

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

4. A builder is asked to replace the guttering on a house. The lengths needed, in metres, are $$0.6,4.0,2.5,3.2,0.5,2.6,0.4,0.3,4.0 \text { and } 1.0$$ Guttering is sold in 4 m lengths.

1. Carry out a quick sort to produce a list of the lengths needed in descending order. You should show the result of each pass and identify your pivots clearly.
2. Apply the first-fit decreasing bin-packing algorithm to your ordered list to determine the total number of 4 m lengths needed.
3. Does the answer to part (b) use the minimum number of 4 m lengths? You must justify your answer.

2. $$\begin{array} { l l l l l l l l } 23 & 29 & 11 & 34 & 10 & 14 & 35 & 17 \end{array}$$ The numbers represent the sizes, in megabytes (MB), of eight files.
The files are to be stored on 50 MB discs.

1. Calculate a lower bound for the number of discs needed to store all eight files.
2. Use the first-fit bin packing algorithm to fit the files onto the discs.
3. Perform a bubble sort on the numbers in the list to sort them into descending order. You need only write down the final result of each pass.
4. Use the first-fit decreasing bin packing algorithm to fit the files onto the discs.

5.

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

5. $$90,50,55,40,20,35,30,25,45$$

1. Use the bubble sort algorithm to sort the list of numbers above into descending order showing the rearranged order after each pass. Jessica wants to record a number of television programmes onto video tapes. Each tape is 2 hours long. The lengths, in minutes, of the programmes she wishes to record are: $$\text { 55, 45, 20, 30, 30, 40, 20, 90, 25, 50, } 35 \text { and } 35 .$$
2. Find the total length of programmes to be recorded and hence determine a lower bound for the number of tapes required.
3. Use the first fit decreasing algorithm to fit the programmes onto her 2-hour tapes. Jessica's friend Amy says she can fit all the programmes onto 4 tapes.
4. Show how this is possible.

1. \(\begin{array} { l l l l l l l l l } 29 & 52 & 73 & 87 & 74 & 47 & 38 & 61 & 41 \end{array}\) The numbers in the list represent the lengths in minutes of nine radio programmes. They are to be recorded onto tapes which each store up to 100 minutes of programmes.

1. Obtain a lower bound for the number of tapes needed to store the nine programmes.
2. Use the first-fit bin packing algorithm to fit the programmes onto the tapes.
3. Use the first-fit decreasing bin packing algorithm to fit the programmes onto the tapes.

1. A carpet fitter needs the following lengths, in metres, of carpet.

$$\begin{array} { l l l l l l l l l } 20 & 33 & 19 & 24 & 31 & 22 & 27 & 18 & 25 \end{array}$$ He cuts them from rolls of length 50 m .

1. Calculate a lower bound for the number of rolls he needs. You must make your method clear.
2. Use the first-fit bin packing algorithm to determine how these lengths can be cut from rolls of length 50 m .
3. Carry out a bubble sort to produce a list of the lengths needed in descending order. You need only give the state of the list after each pass.
4. Apply the first-fit decreasing bin packing algorithm to show how these lengths may be cut from the rolls.
   

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. $$\begin{array} { l l l l l l l l l } 31 & 10 & 38 & 45 & 19 & 47 & 35 & 28 & 12 \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. Carry out a quick sort to produce a list of the numbers in descending order. You should show the result of each pass and identify your pivots clearly.
3. Use the first-fit decreasing bin packing algorithm to determine how the numbers listed can be packed into bins of size 60
4. Determine whether the number of bins used in (c) is optimal. Give a reason for your answer.

6. \(\begin{array} { l l l l l l l l l } 24 & 14 & 8 & x & 19 & 25 & 6 & 17 & 9 \end{array}\) The numbers in the list represent the exact weights, in kilograms, of 9 suitcases. One suitcase is weighed inaccurately and the only information known about the unknown weight, \(x \mathrm {~kg}\), of this suitcase is that \(19 < x \leqslant 23\). The suitcases are to be transported in containers that can hold a maximum of 50 kilograms.

1. Use the first-fit bin packing algorithm, on the list provided, to allocate the suitcases to containers.
2. Using the list provided, carry out a quick sort to produce a list of the weights in descending order. Show the result of each pass and identify your pivots clearly.
3. Apply the first-fit decreasing bin packing algorithm to the ordered list to determine the 2 possible allocations of suitcases to containers. After the first-fit decreasing bin packing algorithm has been applied to the ordered list, one of the containers is full.
4. Calculate the possible integer values of \(x\). You must show your working.

594518553471183171542

1. The list of numbers above is to be sorted into descending order. Perform a quick sort to obtain the sorted list. You should show the result of each pass and identify your pivots clearly. The numbers in the list represent the lengths, in cm, of some pieces of copper wire. The copper wire is sold in one metre lengths.
2. 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.)
3. Determine whether your solution to (b) is optimal. Give a reason for your answer.
   

3. \(\quad \begin{array} { l l l l l l l l l l } 42 & 21 & 15 & 16 & 35 & 10 & 31 & 11 & 27 & 39 \end{array}\)

1. Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 65
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 65 The nine distinct numbers below are to be sorted into descending order $$\begin{array} { l l l l l l l l l } 23 & 14 & 17 & \boldsymbol { x } & 21 & 18 & 8 & 20 & 11 \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 first complete pass, the list is $$\begin{array} { l l l l l l l l l } 23 & 17 & \boldsymbol { x } & 21 & 18 & 14 & 20 & 11 & 8 \end{array}$$ After the second complete pass, the list is $$\begin{array} { l l l l l l l l l } 23 & 17 & 21 & 18 & \boldsymbol { x } & 20 & 14 & 11 & 8 \end{array}$$
4. Using this information, write down the smallest interval that must contain \(\boldsymbol { x }\). Give your answer as an inequality.

2. A list of nine numbers needs to be sorted into descending order.

1. Describe how to carry out the first pass of a bubble sort on the numbers in the list. Mayleen used a sorting algorithm to sort a list of nine numbers into descending order. Mayleen's list after the first pass through the algorithm is given below. $$\begin{array} { l l l l l l l l l } 30 & 33 & 35 & 27 & 20 & 24 & 21 & 15 & 19 \end{array}$$
2. Explain how you know that Mayleen did not use the bubble sort algorithm. Given that Mayleen used the quick sort algorithm,
3. write down the number that was used as a pivot for the first pass,
4. complete the quick sort to obtain a fully sorted list in descending order. You must make your pivots clear.
5. Use the first-fit decreasing bin packing algorithm to determine how the numbers listed can be packed into bins of size 60 A tenth number, 18, is added to the list of nine numbers.
6. Determine whether it is possible to pack the ten numbers into 4 bins of size 60 . You must justify your answer.

4. $$\begin{array} { l l l l l l l l l l l } 25 & 9 & 32 & 16 & 17 & 23 & 18 & 12 & 4 & 8 & 40 \end{array}$$ The numbers in the list represent the weights, in kilograms, of eleven suitcases. The suitcases are to be transported in containers that will each hold a maximum weight of 50 kg .

1. Calculate a lower bound for the number of containers needed. You must make your method clear.
2. Use the first-fit bin packing algorithm to allocate the suitcases to the containers.
3. Carry out a quick sort 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 to allocate the suitcases to the containers. The two heaviest suitcases are replaced with two suitcases both of which weigh \(x \mathrm {~kg}\). It is given that the lower bound for the number of containers needed is now one less than the number found in (a).
5. Determine the range of values for \(x\). You should make your working clear.

6. \(\begin{array} { l l l l l l l l l l } 55 & 80 & 25 & 84 & 25 & 34 & 17 & 75 & 3 & 5 \end{array}\)

1. The list of numbers above is to be sorted into descending order. Perform a bubble sort to obtain the sorted list, giving the state of the list after each complete pass. The numbers in the list represent weights, in grams, of objects which are to be packed into bins that hold up to 100 g .
2. Determine the least number of bins needed.
3. Use the first-fit decreasing algorithm to fit the objects into bins which hold up to 100 g .

5. Nine pieces of wood are required to build a small cabinet. The lengths, in cm, of the pieces of wood are listed below. $$20 , \quad 20 , \quad 20 , \quad 35 , \quad 40 , \quad 50 , \quad 60 , \quad 70 , \quad 75$$ Planks, one metre in length, can be purchased at a cost of \(\pounds 3\) each.

1. The first fit decreasing algorithm is used to determine how many of these planks are to be purchased to make this cabinet. Find the total cost and the amount of wood wasted.
   (5) Planks of wood can also be bought in 1.5 m lengths, at a cost of \(\pounds 4\) each. The cabinet can be built using a mixture of 1 m and 1.5 m planks.
2. Find the minimum cost of making this cabinet. Justify your answer.
   (4)

1. $$\begin{array} { l l l l l l l l l l l } 4 & 6.5 & 7 & 1.3 & 2 & 5 & 1.5 & 6 & 4.5 & 6 & 1 \end{array}$$ The list of eleven numbers shown above is to be sorted into descending order.

1. Carry out a quick sort to produce the sorted list. You should show the result of each pass and identify the pivots clearly.
2. Use the first-fit decreasing bin packing algorithm to pack the numbers into bins of size 10
3. Determine whether your answer to part (b) uses the minimum number of bins. You must justify your answer. A different list of eleven numbers is to be sorted into descending order using a bubble sort. The list after the second pass is
   1.6
   1.7
   1.5
   3.8
   3.3
   4.5
   4.8
   5.6
   5.4
   6.7
   9.1
4. Explain how you know that at least one of the first two passes of the bubble sort was not carried out correctly.

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.

5. The nine distinct numbers in the following list are to be packed into bins of size 50 $$\begin{array} { l l l l l l l l l } 23 & 17 & 19 & x & 24 & 8 & 18 & 10 & 21 \end{array}$$ When the first-fit bin packing algorithm is applied to the numbers in the list it results in the following allocation. Bin 1: 23178
Bin 2: \(19 \quad x \quad 10\) Bin 3: 2418
Bin 4: 21

1. Explain why \(13 < x < 21\) The same list of numbers is to be sorted into descending order. A bubble sort, starting at the left-hand end of the list, is to be used to obtain the sorted list. After the first complete pass the list is $$\begin{array} { l l l l l l l l l } 23 & 19 & 17 & 24 & x & 18 & 10 & 21 & 8 \end{array}$$
2. Using this information, write down the smallest interval that must contain \(x\), giving your answer as an inequality. When the first-fit decreasing bin packing algorithm is applied to the nine distinct numbers it results in the following allocation. Bin 1: 2423
   Bin 2: 211910
   Bin 3: \(1817 x\) Bin 4: 8
   Given that only one of the bins is full and that \(x\) is an integer,
3. calculate the value of \(x\). You must give reasons for your answer.