| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2008 |
| Session | January |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | First-Fit Bin Packing |
| Difficulty | Easy -1.8 This is a straightforward application of standard bin-packing algorithms (first-fit and first-fit decreasing) with small numbers and simple arithmetic. All parts require only direct application of memorized procedures with no problem-solving, insight, or mathematical reasoning beyond basic addition to check capacity constraints. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
Five boxes weigh 5 kg, 2 kg, 4 kg, 3 kg and 8 kg. They are stacked, in the order given, with the first box at the top of the stack. The boxes are to be packed into bins that can each hold up to 10 kg.
\begin{enumerate}[label=(\roman*)]
\item Use the first-fit method to put the boxes into bins. Show clearly which boxes are packed in which bins. [2]
\item Use the first-fit decreasing method to put the boxes into bins. You do not need to use an algorithm for sorting. Show clearly which boxes are packed in which bins. [2]
\item Why might the first-fit decreasing method not be practical? [1]
\item Show that if the bins can only hold up to 8 kg each it is still possible to pack the boxes into three bins. [1]
\end{enumerate}
\hfill \mbox{\textit{OCR D1 2008 Q1 [6]}}