| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2007 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | First-Fit Bin Packing |
| Difficulty | Easy -1.2 This is a straightforward application of standard bin packing algorithms with small numbers requiring only basic arithmetic. Part (i) and (ii) are purely procedural recall, while part (iii) requires minimal problem-solving to find an alternative packing (14+11=25, 9+6+6=21) and observe it splits items between hikers. Well below average difficulty for A-level maths. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Answer | Marks | Guidance |
|---|---|---|
| - 6 litre item does not fit in either rucksack | M1 for applying algorithm | A1 for correct allocation |
| Answer | Marks | Guidance |
|---|---|---|
| - Rucksack 2: 9, 6, 6 (total 21) | B1 for correct descending order | M1 for applying first fit decreasing |
| Answer | Marks | Guidance |
|---|---|---|
| Fairer packing e.g. Rucksack 1: 14, 6 = 20; Rucksack 2: 11, 9, 6 = 26 (or similar more balanced split such as 14, 6, 6 = 26 vs 11, 9 = 20, but difference reduced). Hikers might not want this because one rucksack is heavier/more awkward, or items may not physically fit together | B1 for a valid fairer packing | B1 for valid reason why hikers might not want it |
# Question 2:
## Part (i)
First fit in order 14, 6, 11, 9, 6:
- Rucksack 1: 14, 6 (total 20)
- Rucksack 2: 11, 9 (total 20), 6 doesn't fit
- 6 litre item does not fit in either rucksack | M1 for applying algorithm | A1 for correct allocation | B1 for comment that one item (6 litres) cannot be packed / not all items fit
## Part (ii)
Descending order: 14, 11, 9, 6, 6
- Rucksack 1: 14, 11 (total 25, full)
- Rucksack 2: 9, 6, 6 (total 21) | B1 for correct descending order | M1 for applying first fit decreasing | A1 for correct packing (all items fit)
## Part (iii)
Fairer packing e.g. Rucksack 1: 14, 6 = 20; Rucksack 2: 11, 9, 6 = 26 (or similar more balanced split such as 14, 6, 6 = 26 vs 11, 9 = 20, but difference reduced). Hikers might not want this because one rucksack is heavier/more awkward, or items may not physically fit together | B1 for a valid fairer packing | B1 for valid reason why hikers might not want it
---2 Two hikers each have a 25 litre rucksack to pack. The items to be packed have volumes of 14, 6, 11, 9 and 6 litres.\\
(i) Apply the first fit algorithm to the items in the order given and comment on the outcome.\\
(ii) Write the five items in descending order of volume. Apply the first fit decreasing algorithm to find a packing for the rucksacks.\\
(iii) The hikers argue that the first fit decreasing algorithm does not produce a fair allocation of volumes to rucksacks. Produce a packing which gives a fairer allocation of volumes between the two rucksacks. Explain why the hikers might not want to use this packing.
\hfill \mbox{\textit{OCR MEI D1 2007 Q2 [8]}}