Standard +0.3 This is a straightforward bin packing question testing standard algorithms and basic reasoning. Parts (a)-(c) are routine applications of packing methods, (d) is bookwork, (e) is simple counting, and (f)-(g) require modest logical thinking but no sophisticated insight. The multi-part structure inflates marks but each component is below average difficulty for A-level.
7 Six items need to be packed into bins.
Each bin has size \(k\), where \(k\) is an integer.
The sizes of the items are
\(\begin{array} { l l l l l l } 8 & 5 & 4 & 7 & 3 & 3 \end{array}\)
Show a way to pack the items into two bins of size \(k = 18\).
If exactly three bins are needed, determine the possible values of \(k\).
Use the first-fit method to pack the items into bins of size 12.
Explain why, in general, the first-fit algorithm does not necessarily find the most efficient solution to a packing problem.
A possible way to calculate the run-time of the first-fit method is to count for each item the number of bins, excluding full bins, that are considered before the bin where each item is packed. The total count for all packed items is then used to calculate the run-time of the method.
Determine the total count for the packing used in part (c).
A student says that when \(k = 13\) the total count is 0 because the first bin fills up before the second bin is considered.
Explain why the student's argument is not correct.
Determine the least possible value of \(k\) for which the total count is 0 .
\section*{END OF QUESTION PAPER}
7 Six items need to be packed into bins.
Each bin has size $k$, where $k$ is an integer.
The sizes of the items are\\
$\begin{array} { l l l l l l } 8 & 5 & 4 & 7 & 3 & 3 \end{array}$
\begin{enumerate}[label=(\alph*)]
\item Show a way to pack the items into two bins of size $k = 18$.
\item If exactly three bins are needed, determine the possible values of $k$.
\item Use the first-fit method to pack the items into bins of size 12.
\item Explain why, in general, the first-fit algorithm does not necessarily find the most efficient solution to a packing problem.
A possible way to calculate the run-time of the first-fit method is to count for each item the number of bins, excluding full bins, that are considered before the bin where each item is packed. The total count for all packed items is then used to calculate the run-time of the method.
\item Determine the total count for the packing used in part (c).
A student says that when $k = 13$ the total count is 0 because the first bin fills up before the second bin is considered.
\item Explain why the student's argument is not correct.
\item Determine the least possible value of $k$ for which the total count is 0 .
\section*{END OF QUESTION PAPER}
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete AS 2024 Q7 [13]}}