| Exam Board | OCR |
|---|---|
| Module | Further Discrete (Further Discrete) |
| Year | 2018 |
| Session | March |
| Marks | 6 |
| Topic | Sorting Algorithms |
| Type | First-Fit Decreasing Bin Packing |
| Difficulty | Easy -1.2 This is a straightforward application of a standard bin-packing algorithm (first-fit decreasing) followed by a simple optimization problem with small numbers that can be solved by inspection or trial-and-error. Both parts require only mechanical application of taught procedures with no novel problem-solving or mathematical insight. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Bag | A | B | C | D | E | F | G | H | I | J |
| Mass (kg) | 8 | 10 | 10 | 12 | 12 | 12 | 13 | 15 | 18 | 18 |
| Value | 6 | 3 | 3 | 2 | 4 | 5 | 4 | 6 | 4 | 4 |
| Answer | Marks | Guidance |
|---|---|---|
| Crate 1: 18 18 13; Crate 2: 15 12 12 10; Crate 3: 12 10 8 | M1*, Dep*M1, A1 | First crate starts with 18 18; 15 is in second crate and 13 in first; All correct |
| Answer | Marks | Guidance |
|---|---|---|
| A is the best value per kg. Using packing from part (i), max values of crates 1 and 2 are J, I, G = 12 and H, F, E, C = 18. Put A in crate 2 instead of C to get value 21. | B1, M1, A1 | Include A; Adapting solution from (i) or considering best value per kg; A valid solution (mass of each crate \(\leq 50\), total value of two crates \(\geq 32\)) |
## (i)
| Crate 1: 18 18 13; Crate 2: 15 12 12 10; Crate 3: 12 10 8 | M1*, Dep*M1, A1 | First crate starts with 18 18; 15 is in second crate and 13 in first; All correct |
## (ii)
| A is the best value per kg. Using packing from part (i), max values of crates 1 and 2 are J, I, G = 12 and H, F, E, C = 18. Put A in crate 2 instead of C to get value 21. | B1, M1, A1 | Include A; Adapting solution from (i) or considering best value per kg; A valid solution (mass of each crate $\leq 50$, total value of two crates $\geq 32$) |
---The masses, in kg, of ten bags are given below.
8 \quad 10 \quad 10 \quad 12 \quad 12 \quad 12 \quad 13 \quad 15 \quad 18 \quad 18
\begin{enumerate}[label=(\roman*)]
\item Use first-fit decreasing to pack the bags into crates that can hold a maximum of 50 kg each. [3]
\end{enumerate}
Only two crates are available, so only some of the bags will be packed. Each bag is given a value.
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
Bag & A & B & C & D & E & F & G & H & I & J \\
\hline
Mass (kg) & 8 & 10 & 10 & 12 & 12 & 12 & 13 & 15 & 18 & 18 \\
\hline
Value & 6 & 3 & 3 & 2 & 4 & 5 & 4 & 6 & 4 & 4 \\
\hline
\end{tabular}
\begin{enumerate}[label=(\roman*)]
\setcounter{enumi}{1}
\item Find a packing into two crates so that the total value of the bags in the crates is at least 32. [3]
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete 2018 Q1 [6]}}