7.03m Packing extensions: 2D/3D packing and knapsack problems

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.

4 Jack and Jill are packing food parcels. The boxes for the food parcels can each carry up to 5000 g in weight and can each hold up to \(30000 \mathrm {~cm} ^ { 3 }\) in volume. The number of each item to be packed, their dimensions and weights are given in the table below. Jill tries to pack the items by weight using the first-fit decreasing method.

1. List the 30 items in order of decreasing weight and hence show Jill's packing. Explain why Jill's packing is not possible. Jack tries to pack the items by volume using the first-fit decreasing method.
2. List the 30 items in order of decreasing volume and hence show Jack's packing. Explain why Jack's packing is not possible.
3. Give another reason why a packing may not be possible.

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?

6. Four sales representatives ( \(R _ { 1 } , R _ { 2 } , R _ { 3 }\) and \(R _ { 4 }\) ) are to be sent to four areas ( \(A _ { 1 } , A _ { 2 } , A _ { 3 }\) and \(A _ { 4 }\) ) such that each representative visits one area. The estimated profit, in tens of pounds, that each representative will make in each area is shown in the table below. Use the Hungarian method to obtain an allocation which will maximise the total profit made from the visits. Show the state of the table after each stage in the algorithm.
(13 marks)

5. A construction company has three teams of workers available, each of which is to be assigned to one of four jobs at a site. The following table shows the estimated cost, in tens of pounds, of each team doing each job: Use the Hungarian algorithm to find an allocation of jobs which will minimise the total cost. Show the state of the table after each stage in the algorithm and state the cost of the final assignment.
(13 marks)

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}

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.

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. A travel company offers a touring holiday which stops at four locations, \(A , B , C\) and \(D\). The tour may be taken with the locations appearing in any order, but the number of days spent in each location is dependent on its position in the tour, as shown in the table below. Showing the state of the table at each stage, use the Hungarian algorithm to find the order in which to complete the tour so as to maximise the total number of days. State the maximum total number of days that can be spent in the four locations.

3. Four people are contributing to the entertainment section of an email magazine. For one issue reviews are required for a film, a musical, a ballet and a concert such that each person reviews one show. The people in charge of the magazine will pay each person's expenses and the cost, in pounds, for each reviewer to attend each show are given below. Use the Hungarian algorithm to find an optimal assignment which minimises the total cost. State the total cost of this allocation.

2 Seven items need to be packed into bins. Each bin has capacity 30 kg . The sizes of the items, in kg, in the order that they are received, are as follows.
12
23
15
18
8
7
5

1. Find the packing that results using each of these algorithms.
   1. The next-fit method
   2. The first-fit method
   3. The first-fit decreasing method
2. A student claims that all three methods from part (a) can be used for both 'online' and 'offline' lists. Explain why the student is wrong. The bins of capacity 30 kg are replaced with bins of capacity \(M \mathrm {~kg}\), where \(M\) is an integer.
   The item of size 23 kg can be split into two items, of sizes \(x \mathrm {~kg}\) and \(( 23 - x ) \mathrm { kg }\), where \(x\) may be any integer value you choose from 1 to 11. No other item can be split.
3. Determine the smallest value of \(M\) for which four bins are needed to pack these eight items. Explain your reasoning carefully.