下面列表中的数字代表十个板条箱的重量（单位：千克）。板条箱将用卡车运输，每辆卡车最多可容纳总板条箱重量为 300 kg。

$175 \quad 135 \quad 210 \quad 105 \quad 100 \quad 150 \quad 60 \quad 20 \quad 70 \quad 125$

(a) 计算运输板条箱所需卡车数量的下界。

(b) 使用提供的列表，执行冒泡排序以产生降序的重量列表。只需给出每次传递结束后的列表状态。

(c) 使用首次适应递减装箱算法将板条箱分配给卡车。

先求十个板条箱的总重量，再除以每辆卡车的最大载重。由于卡车数量必须是整数，所得商要向上取整；只写整数 4 而不展示这个计算，并不能充分说明下界的来源。

The total weight of the crates is

Hence

Therefore the lower bound for the number of trucks is

按照降序冒泡排序的比较方向逐趟扫描，相邻两数顺序不合要求时交换。题目只要求每一趟结束后的列表；即使第五趟已经得到有序列表，仍要再做一趟并写出没有发生交换的结果，才能确认排序结束。

The states of the list after successive passes are:

There are no swaps in pass 6, so the sort is complete.

使用 (b) 的降序列表依次放置板条箱。每次都从第一辆卡车开始检查，把当前板条箱放入第一辆仍有足够剩余容量的卡车；只有现有卡车都放不下时才启用新卡车。

Applying first-fit decreasing to

gives

Thus the crates are allocated to $\boxed{4\text{ trucks}}$.