| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2003 |
| Session | November |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | First-Fit Decreasing Bin Packing |
| Difficulty | Moderate -0.8 This is a straightforward application of the first-fit decreasing algorithm with clear numerical values and a simple optimization in part (b). The algorithm is mechanical (sort descending, place items in bins), requires only basic arithmetic, and the optimization involves trying a few combinations of two plank sizes—all standard D1 content with no novel problem-solving insight required. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Answer | Marks | Guidance |
|---|---|---|
| \(\text{Bin } 5 - 20\) | M1, A1, A1 | |
| 5 Planks needed: cost £15 | A1 | |
| \(\text{Wastage} = 5+10+0+15+80 = 110\text{cm}\) | A1 | (5) |
| Answer | Marks |
|---|---|
| \(\text{Bin } 3\ (1\text{m}) - 35+20+20+20\) OR \(\text{Bin } 3\ (1.5\text{m}) -50+40+35+20\) | M1, A1, A1 |
| Cost £11 | A1 |
| 1.5m lengths better value than 1m lengths to use as many as possible | (4) |
# Question 5:
## Part (a)
$\text{Bin } 1 - 75+20$
$\text{Bin } 2 - 70+20$
$\text{Bin } 3 - 60+40$
$\text{Bin } 4 - 50+35$
$\text{Bin } 5 - 20$ | M1, A1, A1 |
5 Planks needed: cost £15 | A1 |
$\text{Wastage} = 5+10+0+15+80 = 110\text{cm}$ | A1 | (5)
## Part (b)
$\text{Bin } 1\ (1.5\text{m}) - 75+70$ OR $\text{Bin } 1\ (1\text{m}) -75+20$
$\text{Bin } 2\ (1.5\text{m}) - 60+50+40$ OR $\text{Bin } 2\ (1.5\text{m}) -70+60+20$
$\text{Bin } 3\ (1\text{m}) - 35+20+20+20$ OR $\text{Bin } 3\ (1.5\text{m}) -50+40+35+20$ | M1, A1, A1 |
Cost £11 | A1 |
1.5m lengths better value than 1m lengths to use as many as possible | (4)
**Total: 9 marks**
---5. Nine pieces of wood are required to build a small cabinet. The lengths, in cm, of the pieces of wood are listed below.
$$20 , \quad 20 , \quad 20 , \quad 35 , \quad 40 , \quad 50 , \quad 60 , \quad 70 , \quad 75$$
Planks, one metre in length, can be purchased at a cost of $\pounds 3$ each.
\begin{enumerate}[label=(\alph*)]
\item The first fit decreasing algorithm is used to determine how many of these planks are to be purchased to make this cabinet. Find the total cost and the amount of wood wasted.\\
(5)
Planks of wood can also be bought in 1.5 m lengths, at a cost of $\pounds 4$ each. The cabinet can be built using a mixture of 1 m and 1.5 m planks.
\item Find the minimum cost of making this cabinet. Justify your answer.\\
(4)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2003 Q5 [9]}}