题目
Problem
The list of numbers shown below represents the masses, in kg, of nine items that are to be moved from one factory to another.
The items will all be moved, by van, at the same time.
Each van can carry at most 600 kg.
(a) Calculate a lower bound for the number of vans required.
(2)
(b) Use the first-fit bin-packing algorithm to allocate the items to vans.
(2)
题目中文翻译
下面的数字列表表示待从一个工厂运送到另一个工厂的九件物品的质量（单位：kg）。
所有物品将同时用货车运送。
每辆货车最多可装载 600 kg。
(a) 计算所需货车数量的下界。
(b) 使用首次适应装箱算法将物品分配到货车。
解答
(a)
解法一
思路
展开
先求九件物品的总质量，再除以每辆货车的最大载重 600 kg。由于货车数量必须是整数，应将所得结果向上取整，得到所需数量的下界。
答题过程
展开
The total mass of the items is
Therefore,
so the lower bound for the number of vans is
(b)
解法一
思路
展开
保持题目给出的物品顺序，不先排序。依次处理每件物品，并从第一辆货车开始检查，把它放入第一辆仍有足够载重空间的货车；若所有已有货车都放不下，才启用新货车。
答题过程
展开
Applying first-fit in the given order gives
| Item (kg) | First available van | Load after placement (kg) |
|---|---|---|
| 180 | 1 | 180 |
| 300 | 1 | 480 |
| 250 | 2 | 250 |
| 410 | 3 | 410 |
| 240 | 2 | 490 |
| 120 | 1 | 600 |
| 230 | 4 | 230 |
| 310 | 4 | 540 |
| 190 | 3 | 600 |
Thus the allocation is
| Van | Items (kg) | Total load (kg) |
|---|---|---|
| 1 | 180, 300, 120 | 600 |
| 2 | 250, 240 | 490 |
| 3 | 410, 190 | 600 |
| 4 | 230, 310 | 540 |