Question 1 · structured
12.5 marksA list of numbers representing the weights (in kg) of 8 packages to be packed into boxes of maximum capacity 20 kg is given below: 11.2, 5.4, 8.5, 3.2, 9.1, 7.6, 4.3, 6.7. (a) Use the Bubble Sort algorithm, sorting into descending order, to show the sorted list. Show the state of the list at the end of each pass. (b) Use the First-Fit Decreasing bin-packing algorithm to pack these packages into the boxes. (c) Determine if this is an optimal packing. Justify your answer.
Show answer & marking schemeHide answer & marking scheme
Worked solution
Let the initial list be: 11.2, 5.4, 8.5, 3.2, 9.1, 7.6, 4.3, 6.7. (a) Bubble Sort descending: Pass 1: Compare adjacent elements and swap if the left is smaller than the right. 11.2 vs 5.4 (no swap), 5.4 vs 8.5 (swap), 5.4 vs 3.2 (no swap), 3.2 vs 9.1 (swap), 3.2 vs 7.6 (swap), 3.2 vs 4.3 (swap), 3.2 vs 6.7 (swap). State at end of Pass 1: 11.2, 8.5, 5.4, 9.1, 7.6, 4.3, 6.7, 3.2. Pass 2: 11.2 vs 8.5 (no swap), 8.5 vs 5.4 (no swap), 5.4 vs 9.1 (swap), 5.4 vs 7.6 (swap), 5.4 vs 4.3 (no swap), 4.3 vs 6.7 (swap). State at end of Pass 2: 11.2, 8.5, 9.1, 7.6, 5.4, 6.7, 4.3, 3.2. Pass 3: 11.2 vs 8.5 (no swap), 8.5 vs 9.1 (swap), 8.5 vs 7.6 (no swap), 7.6 vs 5.4 (no swap), 5.4 vs 6.7 (swap). State at end of Pass 3: 11.2, 9.1, 8.5, 7.6, 6.7, 5.4, 4.3, 3.2. Pass 4: No swaps occur. List is sorted. (b) First-Fit Decreasing: Sorted list is 11.2, 9.1, 8.5, 7.6, 6.7, 5.4, 4.3, 3.2. Capacity = 20. Item 11.2 goes into Box 1 (space left 8.8). Item 9.1 goes into Box 2 (space left 10.9). Item 8.5 goes into Box 3 (space left 11.5). Item 7.6 goes into Box 2 (space left 3.3). Item 6.7 goes into Box 1 (space left 2.1). Item 5.4 goes into Box 3 (space left 6.1). Item 4.3 goes into Box 3 (space left 1.8). Item 3.2 goes into Box 2 (space left 0.1). Final packing: Box 1: [11.2, 6.7], Box 2: [9.1, 7.6, 3.2], Box 3: [8.5, 5.4, 4.3]. (c) Lower bound calculation: Sum of weights = 11.2 + 9.1 + 8.5 + 7.6 + 6.7 + 5.4 + 4.3 + 3.2 = 56.0. Lower bound = 56.0 / 20 = 2.8. Since the lower bound is 2.8, the minimum integer number of boxes needed is 3. Since we achieved packing in 3 boxes, it is optimal.
Marking scheme
Part (a): M1 for a correct first pass of bubble sort. A1 for correct end of Pass 1 state. M1 for Pass 2 and Pass 3. A1 for the correct sorted list. A1 for stating that the algorithm stops after Pass 4 with no swaps. Part (b): M1 for ordering the list first. M1 for placing at least 5 items correctly. A1 for Box 1 and Box 2 correct. A1 for Box 3 correct. Part (c): M1 for calculating the sum and dividing by 20. A1 for correct lower bound of 3. A1 for a clear conclusion linking the lower bound to the number of boxes used.