题目
The numbers below are to be packed into bins of size 60.
35, 17, 10, 7, 28, 23, 41, 15, 20, 29
(a) Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 60.
(b) 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.
(c) 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.
20, 24, 17, 26, 8, 15, x, y, 19, 12
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
24, 26, 20, 17, 15, y, 19, 12, x, 8
(d) Find the constraints on the values of x and y.
(Total 13 marks)
题目中文翻译
以下数字需要装入容量为 60 的箱子中。
35、17、10、7、28、23、41、15、20、29
(a) 使用首次适应装箱算法确定上述数字如何装入容量为 60 的箱子中。
(b) 将数字列表按降序排列。使用快速排序获得排序后的列表。你应该显示每趟的结果并清楚地标出你的基准元素。
(c) 对你的有序列表使用首次适应递减装箱算法，将数字装入容量为 60 的箱子中。
以下十个不同的数字需要按降序排列。
20、24、17、26、8、15、x、y、19、12
使用冒泡排序从列表左端开始获得排序后的列表。
第二趟完整遍历后列表为
24、26、20、17、15、y、19、12、x、8
(d) 求 x 和 y 的取值范围。