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

$14 \quad 20 \quad 23 \quad 17 \quad 15 \quad 22 \quad 19 \quad 25 \quad 13 \quad 28 \quad 32$

所需箱子数量的下界为 4。

(a) 确定 $n$ 的可能取值范围。必须清楚说明方法。

(b) 执行快速排序以产生降序的数字列表。应显示每次传递的结果并清楚地标出枢轴。

当对原始数字列表应用首次适应装箱算法时，获得以下分配。

箱 1：$14 \quad 20 \quad 23 \quad 15$

箱 2：$17 \quad 22 \quad 19 \quad 13$

箱 3：$25 \quad 28$

箱 4：$32$

当对排序后的数字列表应用首次适应递减装箱算法时，获得以下分配。

箱 1：$32 \quad 28$

箱 2：$25 \quad 23 \quad 22$

箱 3：$20 \quad 19 \quad 17 \quad 15$

箱 4：$14 \quad 13$

(c) 确定 $n$ 的值。必须完全解释推理过程。

所有数的总和为 228。箱数下界为 4，表示总重量除以箱子容量后大于 3 且不超过 4。利用 $n>0$ 解这个双重不等式，再结合 $n$ 是正整数写出范围。

The total of the numbers is $228$. Since the lower bound is $4$,

As $n>0$,

Therefore

Since $n$ is an integer,

采用 middle-right 规则选枢轴，并按降序排列：大于枢轴的数放在左侧，小于枢轴的数放在右侧。对每个尚未排好的子列表继续使用相同规则；竖线表示枢轴已经固定。

Using middle-right pivots, the initial pivot is $22$.

Using pivots $28$ and $15$ gives

Using pivots $25$, $17$ and $13$ gives

Finally, using pivot $19$ gives

也可以一致地采用 middle-left 规则。第一次仍以 22 为枢轴；之后各子列表的枢轴选择会不同，但最终降序列表不变。

Using middle-left pivots, the initial pivot is $22$.

Using pivots $25$ and $17$ gives

Using pivots $28$, $20$ and $15$ gives

Finally, using pivot $14$ gives

先用 first-fit 的 Bin 1 得到容量只能是 72 或 73：其中已有数的总和为 72，而先前尝试放入的 17 会令总和达到 74，所以它放不下。再看 first-fit decreasing 的 Bin 1，若容量是 73，最后的 13 应能与 32、28 同箱；实际没有放入，因此容量小于 73。两项条件合起来唯一可能是 72。

In the first-fit packing, Bin 1 contains

so $n\geq72$. The value $17$ was considered before $15$ but did not fit in Bin 1, and

Hence $n<74$. Since $n$ is an integer,

In the first-fit decreasing packing, Bin 1 contains $32$ and $28$, but the later value $13$ does not fit there. Therefore

so $n<73$. Combining the conditions,