下面列表中的十二个数字要装入大小为 $n$ 的箱子中，其中 $n$ 是正整数。

$28 \quad 31 \quad 5 \quad 25 \quad 16 \quad 35 \quad 18 \quad 22 \quad 11 \quad 27 \quad 15 \quad 13$

当对列表应用首次适应装箱算法时，得到以下分配。

箱 1：$28 \quad 31 \quad 5$

箱 2：$25 \quad 16 \quad 18 \quad 11$

箱 3：$35 \quad 22 \quad 15$

箱 4：$27 \quad 13$

(a) 根据上面显示的装箱，确定 $n$ 的可能值。必须给出理由。

(b) 原始的十二个数字列表要按升序排序。使用快速排序获得排序后的列表。应显示每次传递的结果并清楚地标出枢轴。

当对列表应用首次适应递减装箱算法时，得到以下分配。

箱 1：$35 \quad 31 \quad 5$

箱 2：$28 \quad 27 \quad 16$

箱 3：$25 \quad 22 \quad 18$

箱 4：$15 \quad 13 \quad 11$

(c) 确定 $n$ 的值。必须给出理由。

先由各箱总和确定容量的下界：任何箱子的总和都不能超过 $n$。再利用首次适应规则确定上界：处理到 11 时，第一箱已有 64；由于 11 没有放入第一箱，说明第一箱放不下它。最后结合 $n$ 为正整数列出所有可能值。

Bin 3 has total

so

When 11 was considered, Bin 1 already contained $28$, $31$ and $5$, with total 64. Since first-fit did not place 11 in Bin 1,

so $n<75$. As $n$ is an integer,

采用官方评分资料中的 middle-right 规则：偶数长度子列选择中间两个元素中的右侧元素作基准。每轮同时处理所有未完成子列，把小于基准的数放在左侧、大于基准的数放在右侧，直到列表升序排列。

Using middle-right pivots, begin with pivot 18.

Pass 1:

5  16  11  15  13  |18|  28  31  25  35  22  27

The next pivots are 11 and 35.

Pass 2:

5  |11|  16  15  13  |18|  28  31  25  22  27  |35|

The next pivots are 15 and 25.

Pass 3:

5  11  13  |15|  16  18  22  |25|  28  31  27  35

The next nontrivial pivot is 31.

Pass 4:

5  11  13  15  16  18  22  25  28  27  |31|  35

The next pivot is 27.

Pass 5:

5  11  13  15  16  18  22  25  |27|  28  31  35

Hence the ascending list is

也可使用官方提供的 middle-left 路线：偶数长度子列选中间左项。只要所有后续子列持续使用同一规则，最终会得到相同的升序列表。

Using middle-left pivots, begin with pivot 35.

Pass 1:

28  31  5  25  16  18  22  11  27  15  13  |35|

The next pivot is 18.

Pass 2:

5  16  11  15  13  |18|  28  31  25  22  27  35

The next pivots are 11 and 25.

Pass 3:

5  |11|  16  15  13  18  22  |25|  28  31  27  35

The next pivots are 15 and 31.

Pass 4:

5  11  13  |15|  16  18  22  25  28  27  |31|  35

The next nontrivial pivot is 28.

Pass 5:

5  11  13  15  16  18  22  25  27  |28|  31  35

Therefore,

在首次适应递减过程中，28 和 27 已使第二箱总和达到 55。随后处理 18 时，它没有进入第二箱而进入第三箱，说明 $55+18$ 已超过容量。把这个新上界与 (a) 的三个候选整数结合即可唯一确定 $n$。

After 28 and 27 have been placed in Bin 2, its total is 55. The item 18 is later placed in Bin 3 rather than Bin 2, so

Therefore $n<73$. From part (a), $n$ is one of 72, 73 and 74, hence