题目 1 · structured
12.5 分A list of eight numbers representing the weights, in grams, of items to be packed into bins of capacity 40 g is given below:
\[15, \quad 27, \quad 12, \quad 19, \quad 8, \quad 22, \quad 14, \quad 18\]
(a) Calculate a lower bound for the number of bins of capacity 40 g required to pack these items. (2)
(b) Perform a Quick Sort to sort the list into descending order. You should show the state of the list after each completed pass and clearly identify the pivot(s) used. You must use the middle item of any sublist (or the left-hand middle item if the sublist has an even number of elements) as the pivot. (5)
(c) Use the first-fit decreasing bin-packing algorithm to pack the sorted items into bins of capacity 40 g. (3.5)
(d) State whether your packing in part (c) is optimal, giving a clear reason. (2)
\[15, \quad 27, \quad 12, \quad 19, \quad 8, \quad 22, \quad 14, \quad 18\]
(a) Calculate a lower bound for the number of bins of capacity 40 g required to pack these items. (2)
(b) Perform a Quick Sort to sort the list into descending order. You should show the state of the list after each completed pass and clearly identify the pivot(s) used. You must use the middle item of any sublist (or the left-hand middle item if the sublist has an even number of elements) as the pivot. (5)
(c) Use the first-fit decreasing bin-packing algorithm to pack the sorted items into bins of capacity 40 g. (3.5)
(d) State whether your packing in part (c) is optimal, giving a clear reason. (2)
查看答案详解收起答案详解
解题
(a) Sum of items = \(15 + 27 + 12 + 19 + 8 + 22 + 14 + 18 = 135\).
Lower bound = \(\lceil 135 / 40 \rceil = \lceil 3.375 \rceil = 4\).
(b) Quick Sort (descending order):
Initial list: \([15, 27, 12, 19, 8, 22, 14, 18]\)
Length 8: Left middle is 19 (4th element). Pivot is 19.
- Pass 1 (comparing items to 19: larger to left, smaller to right):
\(27, 22, [19], 15, 12, 8, 14, 18\)
Now sublists are \([27, 22]\) and \([15, 12, 8, 14, 18]\).
For \([27, 22]\), length 2, pivot is 27.
For \([15, 12, 8, 14, 18]\), length 5, pivot is 8 (3rd element).
- Pass 2:
\([27], 22, [19], 15, 12, 14, 18, [8]\)
Note: 22 and 8 are also now selected as pivots as they are single-element sublists/pivots.
Now remaining sublist to sort is \([15, 12, 14, 18]\), length 4, left middle is 12 (2nd element). Pivot is 12.
- Pass 3:
\(27, 22, 19, 15, 14, 18, [12], 8\)
Now remaining sublist to sort is \([15, 14, 18]\), length 3, pivot is 14 (2nd element).
- Pass 4:
\(27, 22, 19, 15, 18, [14], 12, 8\)
Now remaining sublist to sort is \([15, 18]\), length 2, pivot is 15 (1st element).
- Pass 5:
\(27, 22, 19, 18, [15], 14, 12, 8\)
All elements have been pivots. Sorted list is:
\(27, 22, 19, 18, 15, 14, 12, 8\)
(c) First-Fit Decreasing:
- Item 27: Bin 1 (space left: 13)
- Item 22: Bin 2 (space left: 18)
- Item 19: Bin 3 (space left: 21)
- Item 18: Bin 2 (space left: 0)
- Item 15: Bin 3 (space left: 6)
- Item 14: Bin 4 (space left: 26)
- Item 12: Bin 1 (space left: 1)
- Item 8: Bin 4 (space left: 18)
Final Packing:
Bin 1: 27, 12
Bin 2: 22, 18
Bin 3: 19, 15
Bin 4: 14, 8
(d) The packing is optimal because the number of bins used (4) is equal to the calculated lower bound (4). It is impossible to use fewer than 4 bins.
Lower bound = \(\lceil 135 / 40 \rceil = \lceil 3.375 \rceil = 4\).
(b) Quick Sort (descending order):
Initial list: \([15, 27, 12, 19, 8, 22, 14, 18]\)
Length 8: Left middle is 19 (4th element). Pivot is 19.
- Pass 1 (comparing items to 19: larger to left, smaller to right):
\(27, 22, [19], 15, 12, 8, 14, 18\)
Now sublists are \([27, 22]\) and \([15, 12, 8, 14, 18]\).
For \([27, 22]\), length 2, pivot is 27.
For \([15, 12, 8, 14, 18]\), length 5, pivot is 8 (3rd element).
- Pass 2:
\([27], 22, [19], 15, 12, 14, 18, [8]\)
Note: 22 and 8 are also now selected as pivots as they are single-element sublists/pivots.
Now remaining sublist to sort is \([15, 12, 14, 18]\), length 4, left middle is 12 (2nd element). Pivot is 12.
- Pass 3:
\(27, 22, 19, 15, 14, 18, [12], 8\)
Now remaining sublist to sort is \([15, 14, 18]\), length 3, pivot is 14 (2nd element).
- Pass 4:
\(27, 22, 19, 15, 18, [14], 12, 8\)
Now remaining sublist to sort is \([15, 18]\), length 2, pivot is 15 (1st element).
- Pass 5:
\(27, 22, 19, 18, [15], 14, 12, 8\)
All elements have been pivots. Sorted list is:
\(27, 22, 19, 18, 15, 14, 12, 8\)
(c) First-Fit Decreasing:
- Item 27: Bin 1 (space left: 13)
- Item 22: Bin 2 (space left: 18)
- Item 19: Bin 3 (space left: 21)
- Item 18: Bin 2 (space left: 0)
- Item 15: Bin 3 (space left: 6)
- Item 14: Bin 4 (space left: 26)
- Item 12: Bin 1 (space left: 1)
- Item 8: Bin 4 (space left: 18)
Final Packing:
Bin 1: 27, 12
Bin 2: 22, 18
Bin 3: 19, 15
Bin 4: 14, 8
(d) The packing is optimal because the number of bins used (4) is equal to the calculated lower bound (4). It is impossible to use fewer than 4 bins.
评分标准
(a) M1: For sum of weights divided by 40.
A1: For correct lower bound of 4 (must show working).
(b) M1: First pass complete, 19 correctly placed as pivot with larger items to the left and smaller to the right.
A1: Second pass complete with pivots 27 and 8 identified correctly.
A1: Third pass complete with pivot 12 identified correctly.
A1: Fourth and fifth passes complete with pivots 14 and 15 identified correctly.
A1: Final sorted list fully correct and all pivots shown.
(c) M1: First 4 items (27, 22, 19, 18) placed correctly (18 must go into Bin 2).
A1: Item 15 and 14 placed correctly.
A1: Items 12 and 8 placed correctly, completing the four bins.
(d) B1: States 'Optimal'.
B1: Gives a valid reason referencing the lower bound of 4 calculated in part (a).
A1: For correct lower bound of 4 (must show working).
(b) M1: First pass complete, 19 correctly placed as pivot with larger items to the left and smaller to the right.
A1: Second pass complete with pivots 27 and 8 identified correctly.
A1: Third pass complete with pivot 12 identified correctly.
A1: Fourth and fifth passes complete with pivots 14 and 15 identified correctly.
A1: Final sorted list fully correct and all pivots shown.
(c) M1: First 4 items (27, 22, 19, 18) placed correctly (18 must go into Bin 2).
A1: Item 15 and 14 placed correctly.
A1: Items 12 and 8 placed correctly, completing the four bins.
(d) B1: States 'Optimal'.
B1: Gives a valid reason referencing the lower bound of 4 calculated in part (a).