题目

Problem

The numbers in the list represent the weights, in kilograms, of twelve parcels. The parcels are to be transported in containers that will each hold a maximum weight of 45 kg.

$16 \quad 23 \quad 18 \quad 9 \quad 4 \quad 20 \quad 35 \quad 5 \quad 17 \quad 13 \quad 6 \quad 11$

(a) Calculate a lower bound for the number of containers needed. You must make your method clear.

(2)

(b) Use the first-fit bin packing algorithm to allocate the parcels to the containers.

(3)

(c) Carry out a bubble sort, starting at the left-hand end of the list, to produce a list of the weights in descending order. You should only give the state of the list after each pass.

(4)

(d) Use the first-fit decreasing bin packing algorithm to allocate the parcels to the containers.

(3)

题目中文翻译

列表中的数字代表十二个包裹的重量（单位：千克）。包裹将用容器运输，每个容器最多可容纳 45 kg。

$16 \quad 23 \quad 18 \quad 9 \quad 4 \quad 20 \quad 35 \quad 5 \quad 17 \quad 13 \quad 6 \quad 11$

(a) 计算所需容器数量的下界。必须清楚说明方法。

(b) 使用首次适应装箱算法将包裹分配给容器。

(d) 使用首次适应递减装箱算法将包裹分配给容器。

解答

(a)

解法一

思路

展开

先求所有包裹的总重量，再除以每个容器的最大承重。由于容器数必须是整数，所得商若不是整数，就要向上取整。

答题过程

展开

The total weight is

16+23+18+9+4+20+35+5+17+13+6+11=177\text{ kg}.

Hence

\frac{177}{45}=3.933\ldots

Therefore the lower bound for the number of containers is

\boxed{4}.

(b)

解法一

思路

展开

按题目给出的顺序逐件处理包裹。每次都从第一个容器开始检查，把包裹放入第一个仍有足够容量的容器；若所有已开启的容器都放不下，才开启新容器。

答题过程

展开

Applying the first-fit bin packing algorithm gives:

Container	Parcels (kg)	Total (kg)
1	$16,23,4$	$43$
2	$18,9,5,13$	$45$
3	$20,17,6$	$43$
4	$35$	$35$
5	$11$	$11$

Thus the first-fit allocation uses

\boxed{5\text{ containers}}.

(c)

解法一

思路

展开

要得到降序列表，从左端开始逐对比较相邻元素；若左边小于右边，就交换两者。每一趟结束后，当前最小的未排序元素会移动到未排序部分的最右端。题目只要求写每一趟结束后的列表，并且最后要再写一趟无交换的结果，以确认排序完成。

答题过程

展开

The states of the list after successive passes are:

Pass 1:

\begin{aligned} &\,23,18,16,9,20,35, \\ &\,5,17,13,6,11,4 \end{aligned}

Pass 2:

\begin{aligned} &\,23,18,16,20,35,9, \\ &\,17,13,6,11,5,4 \end{aligned}

Pass 3:

\begin{aligned} &\,23,18,20,35,16,17, \\ &\,13,9,11,6,5,4 \end{aligned}

Pass 4:

\begin{aligned} &\,23,20,35,18,17,16, \\ &\,13,11,9,6,5,4 \end{aligned}

Pass 5:

\begin{aligned} &\,23,35,20,18,17,16, \\ &\,13,11,9,6,5,4 \end{aligned}

Pass 6:

\begin{aligned} &\,35,23,20,18,17,16, \\ &\,13,11,9,6,5,4 \end{aligned}

Pass 7 (no swaps):

\begin{aligned} &\,35,23,20,18,17,16, \\ &\,13,11,9,6,5,4 \end{aligned}

Therefore the list in descending order is

\boxed{35,23,20,18,17,16,13,11,9,6,5,4}.

(d)

解法一

思路

展开

先使用 (c) 的降序列表，再按首次适应规则依次装箱。每件包裹仍要从第一个容器开始尝试，而不是直接放入当前最后一个容器。

答题过程

展开

Using the descending list from part (c), the first-fit decreasing allocation is:

Container	Parcels (kg)	Total (kg)
1	$35,9$	$44$
2	$23,20$	$43$
3	$18,17,6,4$	$45$
4	$16,13,11,5$	$45$

Therefore first-fit decreasing uses

\boxed{4\text{ containers}}.

IAL 2021 June D1 Q1

题目

解答

(a)

解法一

思路

答题过程

(b)

解法一

思路

答题过程

(c)

解法一

思路

答题过程

(d)

解法一

思路

答题过程