题目

Problem

\begin{align*} &\,16\quad23\quad18\quad9\\ &\,\hspace{2pt}4\quad20\quad35\quad5\\ &\,\hspace{4pt}17\quad13\quad6\quad11 \end{align*}

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.

(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。

\begin{align*} &\,16\quad23\quad18\quad9\\ &\,\hspace{2pt}4\quad20\quad35\quad5\\ &\,\hspace{4pt}17\quad13\quad6\quad11 \end{align*}

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

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

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

解答

(a)

解法一

思路

展开

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

答题过程

展开

The total weight is

\begin{align*} &\,16+23+18+9\\ &\,\hspace{2pt}+4+20+35+5\\ &\,\hspace{4pt}+17+13+6+11\\ =&\,177\text{ kg}. \end{align*}

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{ \begin{gathered} 35,23,20,18,17,16,\\ 13,11,9,6,5,4 \end{gathered} }.

解法二

思路

展开

也可以先从左端开始，按升序规则进行冒泡排序：若左边大于右边，就交换两者，每一趟把当前最大的未排序元素移到右端。完成升序排序后，再把整个列表反转，才能得到题目要求的降序列表；不能只写“需要反转”而不写反转后的结果。

答题过程

展开

First carry out a bubble sort into ascending order, starting at the left-hand end. The states after successive passes are:

Pass 1:

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

Pass 2:

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

Pass 3:

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

Pass 4:

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

Pass 5:

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

Pass 6:

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

Pass 7:

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

Pass 8:

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

Pass 9 (no swaps):

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

Reversing the completed ascending list gives the required descending list:

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

(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}}.

D1 2021 June Q1

题目

解答

(a)

解法一

思路

答题过程

(b)

解法一

思路

答题过程

(c)

解法一

思路

答题过程

解法二

思路

答题过程

(d)

解法一

思路

答题过程