| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2010 |
| Session | January |
| Marks | 11 |
| 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 two constraints (weight and volume). Students must list items, apply the standard algorithm twice, and identify why each fails—requiring only mechanical execution of a taught procedure and observation that one constraint is violated while the other is satisfied. The conceptual demand is low for D1 students who have practiced this algorithm. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin7.03m Packing extensions: 2D/3D packing and knapsack problems |
| Item type | \(A\) | \(B\) | \(C\) | \(D\) |
| Number to be packed | 15 | 8 | 3 | 4 |
| Length (cm) | 10 | 40 | 20 | 10 |
| Width (cm) | 10 | 30 | 50 | 40 |
| Height (cm) | 10 | 20 | 10 | 10 |
| Volume ( \(\mathrm { cm } ^ { 3 }\) ) | 1000 | 24000 | 10000 | 4000 |
| Weight (g) | 1000 | 250 | 300 | 400 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Items listed in decreasing weight order: \(A(1000g) \times 15\), \(D(400g)\times4\), \(C(300g)\times3\), \(B(250g)\times8\) | M1 | |
| First-fit decreasing packing shown | A1 | |
| At some point a box exceeds 5000g limit | A1 | |
| Explanation that packing is impossible | B1 B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Items in decreasing volume: \(B(24000)\times8\), \(C(10000)\times3\), \(D(4000)\times4\), \(A(1000)\times15\) | M1 | |
| First-fit decreasing packing shown | A1 A1 | |
| A box exceeds \(30000\text{ cm}^3\) | A1 | |
| Explanation packing impossible | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| A single item exceeds the box capacity (e.g. item \(B\) has volume \(24000\text{ cm}^3\) but weight 250g — or dimensional issue) | B1 | Accept other valid reasons |
# Question 4:
## Part (i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Items listed in decreasing weight order: $A(1000g) \times 15$, $D(400g)\times4$, $C(300g)\times3$, $B(250g)\times8$ | M1 | |
| First-fit decreasing packing shown | A1 | |
| At some point a box exceeds 5000g limit | A1 | |
| Explanation that packing is impossible | B1 B1 | |
## Part (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Items in decreasing volume: $B(24000)\times8$, $C(10000)\times3$, $D(4000)\times4$, $A(1000)\times15$ | M1 | |
| First-fit decreasing packing shown | A1 A1 | |
| A box exceeds $30000\text{ cm}^3$ | A1 | |
| Explanation packing impossible | B1 | |
## Part (iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| A single item exceeds the box capacity (e.g. item $B$ has volume $24000\text{ cm}^3$ but weight 250g — or dimensional issue) | B1 | Accept other valid reasons |
---4 Jack and Jill are packing food parcels. The boxes for the food parcels can each carry up to 5000 g in weight and can each hold up to $30000 \mathrm {~cm} ^ { 3 }$ in volume.
The number of each item to be packed, their dimensions and weights are given in the table below.
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
Item type & $A$ & $B$ & $C$ & $D$ \\
\hline
Number to be packed & 15 & 8 & 3 & 4 \\
\hline
Length (cm) & 10 & 40 & 20 & 10 \\
\hline
Width (cm) & 10 & 30 & 50 & 40 \\
\hline
Height (cm) & 10 & 20 & 10 & 10 \\
\hline
Volume ( $\mathrm { cm } ^ { 3 }$ ) & 1000 & 24000 & 10000 & 4000 \\
\hline
Weight (g) & 1000 & 250 & 300 & 400 \\
\hline
\end{tabular}
\end{center}
Jill tries to pack the items by weight using the first-fit decreasing method.\\
(i) List the 30 items in order of decreasing weight and hence show Jill's packing. Explain why Jill's packing is not possible.
Jack tries to pack the items by volume using the first-fit decreasing method.\\
(ii) List the 30 items in order of decreasing volume and hence show Jack's packing. Explain why Jack's packing is not possible.\\
(iii) Give another reason why a packing may not be possible.
\hfill \mbox{\textit{OCR D1 2010 Q4 [11]}}