| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2009 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | First-Fit Bin Packing |
| Difficulty | Moderate -0.8 This is a straightforward application of standard bin-packing algorithms taught in D1. Part (a) requires simple arithmetic (sum/capacity), part (b) is mechanical application of first-fit algorithm, and part (c) uses the full-bins heuristic which is also routine. No problem-solving insight needed, just following learned procedures. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: \(\frac{230}{60} = 3.83\) so 4 needed | M1 A1 | (2) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: Bin 1: 32 17 9; Bin 2: 45 12; Bin 3: 23 28; Bin 4: 38 16; Bin 5: 10 | M1 A1; A1; A1 | (4) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: e.g. Bin 1: 32 28; Bin 2: 38 12 10; Bin 3: 45 9; Bin 4: 23 17 16 | M1 A1 | (3) |
**Part (a)**
Answer: $\frac{230}{60} = 3.83$ so 4 needed | M1 A1 | (2) | 1M1: Their 230 divided by 60, some evidence of correct method 3.8 enough. 1A1: cso 4.
**Part (b)**
Answer: Bin 1: 32 17 9; Bin 2: 45 12; Bin 3: 23 28; Bin 4: 38 16; Bin 5: 10 | M1 A1; A1; A1 | (4) | 1M1: Use of first fit. Probably 32, 45 and 17 correctly placed. 1A1: = 32, 45, 17, 23, 38, 28, 16, 9 placed correctly. 2A1: 32, 45, 17, 23, 38, 28, 16, 9 placed correctly. 3A1: cao.
**Part (c)**
Answer: e.g. Bin 1: 32 28; Bin 2: 38 12 10; Bin 3: 45 9; Bin 4: 23 17 16 | M1 A1 | (3) | 1M1: Use of full bin – at least one full bin found and 5 numbers placed. 1A1: 2 full bins found. Eg [$32+28$ and $38+12+10$] [$23+28+9$ and $16+12+32$] [$32+28$ and $23+16+12+9$]. 2A1: A 4 bin solution found. Special case for (b) **misread using first fit decreasing**: Give M1A1 (max); Bin 1: 45 12; Bin 2: 38 17; Bin 3: 32 28; Bin 4: 23 16 10 9; M1 for placing 45, 38, 32, 28 and 23 correctly; A1 for cao.
---2.\\
32\\
45\\
17\\
23\\
38\\
28\\
16\\
9\\
12\\
10
The numbers in the list above represent the lengths, in metres, of ten lengths of fabric. They are to be cut from rolls of fabric of length 60 m .
\begin{enumerate}[label=(\alph*)]
\item Calculate a lower bound for the number of rolls needed.
\item Use the first-fit bin packing algorithm to determine how these ten lengths can be cut from rolls of length 60 m .
\item Use full bins to find an optimal solution that uses the minimum number of rolls.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2009 Q2 [9]}}