| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | First-Fit Decreasing Bin Packing |
| Difficulty | Moderate -0.8 This is a standard textbook exercise on bin packing algorithms requiring straightforward application of first-fit decreasing and full-bin methods. The calculations are routine (adding to 24), the algorithms are mechanical to apply, and no novel problem-solving insight is needed—just careful execution of learned procedures. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Answer | Marks |
|---|---|
| Total of lengths = 96 m; \(96 \div 24 = 4\) therefore least no. of rolls = 4 | A1 |
| Answer | Marks |
|---|---|
| Therefore 5 rolls needed | M2 A1 |
| Answer | Marks |
|---|---|
| Full-bins: (14 + 6 + 4), (14 + 6 + 4), (12 + 6 + 6) and (8 + 8 + 8) | M1 A1 |
| Answer | Marks | Guidance |
|---|---|---|
| First-fit decreasing algorithm does not always give an optimal solution | B1 | (7) |
**Part (a)**
Total of lengths = 96 m; $96 \div 24 = 4$ therefore least no. of rolls = 4 | A1 |
**Part (b)**
By inspection we have: 14, 14, 12, 8, 8, 8, 6, 6, 6, 6, 4, 4
[Diagram shows bins with widths and heights appropriately labeled]
Therefore 5 rolls needed | M2 A1 |
**Part (c)**
Full-bins: (14 + 6 + 4), (14 + 6 + 4), (12 + 6 + 6) and (8 + 8 + 8) | M1 A1 |
**Part (d)**
First-fit decreasing algorithm does not always give an optimal solution | B1 | (7) |
---\begin{enumerate}
\item The following lengths of cloth (in metres) are to be cut from standard 24 metre rolls.
\end{enumerate}
$$\begin{array} { l l l l l l l l l l l l }
6 & 6 & 4 & 6 & 8 & 8 & 4 & 12 & 14 & 6 & 14 & 8
\end{array}$$
(a) Considering only the total amount, what is the least number of rolls that are needed?\\
(b) Using the first-fit decreasing algorithm, show that the lengths could be cut from 5 rolls.\\
(c) Using "full-bin" combinations show that it is possible to cut these lengths from the number of rolls found in part (a).\\
(d) Comment on this result.\\
\hfill \mbox{\textit{Edexcel D1 Q2 [7]}}