以下十一个数字列表需要装入容量为 14 的箱子中

$5.2 \quad 4.7 \quad 6.5 \quad 4.5 \quad 3.1 \quad 5.1 \quad 1.8 \quad 2.9 \quad 3.4 \quad 3.8 \quad 1.2$

(a) 使用首次适应装箱算法确定上述十一个数字如何装入容量为 14 的箱子。

(b) 数字列表需要按升序排列。使用快速排序获得排序后的列表。应显示每轮后的结果并清楚标明基准元素。

(c) 对排序后的列表应用首次适应递减装箱算法，将数字装入容量为 14 的箱子。

(d) 解释为什么 (c) 中使用的箱子数量是最优的。

(e) 使用二分搜索算法尝试在数字列表中定位 3.0。清楚说明如何选择基准元素以及每个阶段被排除的列表部分。

保持原顺序逐个处理数字。每个数字都从第一个箱子开始检查，并放入第一个剩余容量足够的箱子；只有所有已有箱子都放不下时才开启新箱子。

Applying first-fit in the given order gives

Thus the packing is

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

Using middle-right pivots, begin with pivot 5.1.

Pass 1:

4.7  4.5  3.1  1.8  2.9  3.4  3.8  1.2  |5.1|  5.2  6.5

The next pivots are 2.9 and 6.5.

Pass 2:

1.8  1.2  |2.9|  4.7  4.5  3.1  3.4  3.8  |5.1|  5.2  |6.5|

The next nontrivial pivots are 1.2 and 3.1; the one-element partition 5.2 is already sorted.

Pass 3:

|1.2|  1.8  |2.9|  |3.1|  4.7  4.5  3.4  3.8  |5.1|  5.2  6.5

The next nontrivial pivot is 3.4; the one-element partition 1.8 is already sorted.

Pass 4:

1.2  1.8  2.9  3.1  |3.4|  4.7  4.5  3.8  5.1  5.2  6.5

The next pivot is 4.5.

Pass 5:

1.2  1.8  2.9  3.1  3.4  3.8  |4.5|  4.7  5.1  5.2  6.5

Hence the ascending list is

也可采用官方认可的 middle-left 规则：偶数长度子列选择中间两个元素中的左侧元素。后续每个子列持续使用同一规则，也会得到相同的升序结果。

Using middle-left pivots, begin with pivot 5.1.

Pass 1:

4.7  4.5  3.1  1.8  2.9  3.4  3.8  1.2  |5.1|  5.2  6.5

The next pivots are 1.8 and 5.2.

Pass 2:

1.2  |1.8|  4.7  4.5  3.1  2.9  3.4  3.8  |5.1|  |5.2|  6.5

The next nontrivial pivot is 3.1; the one-element partitions 1.2 and 6.5 are already sorted.

Pass 3:

1.2  1.8  2.9  |3.1|  4.7  4.5  3.4  3.8  5.1  5.2  6.5

The next nontrivial pivot is 4.5; the one-element partition 2.9 is already sorted.

Pass 4:

1.2  1.8  2.9  3.1  3.4  3.8  |4.5|  4.7  5.1  5.2  6.5

The next nontrivial pivot is 3.4; the one-element partition 4.7 is already sorted.

Pass 5:

1.2  1.8  2.9  3.1  |3.4|  3.8  4.5  4.7  5.1  5.2  6.5

Therefore,

首次适应递减算法先把数字改为降序，再按首次适应规则依次装箱。每个数字仍须从第一个箱子开始检查，不能任意重排以凑出组合。

Use the descending order

First-fit decreasing gives

用全部数字的总和除以每箱容量，得到任何装箱方案都不能突破的箱数下界。若此下界向上取整正好等于 (c) 使用的箱数，就证明该方案最优。

The total size of all the items is 42.2, and

Therefore at least four bins are required. Since the packing in part (c) uses four bins, it is optimal.

在 (b) 的升序列表中进行二分搜索。每次选择当前子列的中间项；若剩余项数为偶数，则采用 middle-right。将 3.0 与基准比较并舍弃不可能包含它的一半，直到只剩一个仍不相等的数。

Number the ascending list from 1 to 11.

1. The first pivot is item 6, which is 3.8. Since $3.8>3.0$, reject items 6 to 11.
2. From items 1 to 5, the pivot is item 3, which is 2.9. Since $2.9<3.0$, reject items 1 to 3.
3. From items 4 and 5, take the middle-right pivot, item 5, which is 3.4. Since $3.4>3.0$, reject item 5.
4. The only remaining item is item 4, which is 3.1. Since $3.1\neq3.0$,