| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming order sequencing |
| Difficulty | Moderate -0.8 This is a straightforward 0/1 knapsack problem with only 5 items, solved by exhaustive enumeration via tree diagram. The method is given (draw branches, terminate when capacity exceeded), requiring systematic application rather than algorithmic insight. Significantly easier than average A-level questions as it's purely mechanical execution with small numbers. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Design | Kendal | Milverton | Arlington | Elford | Grosvenor |
| Plot area ('000 \(\mathrm { m } ^ { 2 }\) ) | 3 | 11 | 3 | 5 | 10 |
| Value ( \(\pounds ^ { \prime } 000 \mathrm {~s}\) ) | 100 | 190 | 40 | 80 | 120 |
2. This question should be answered on the sheet provided.
A builder is going to put up houses on a plot of land of area $12000 \mathrm {~m} ^ { 2 }$.\\
There are 5 designs to choose from and no more than one of each design can be built.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
Design & Kendal & Milverton & Arlington & Elford & Grosvenor \\
\hline
Plot area ('000 $\mathrm { m } ^ { 2 }$ ) & 3 & 11 & 3 & 5 & 10 \\
\hline
Value ( $\pounds ^ { \prime } 000 \mathrm {~s}$ ) & 100 & 190 & 40 & 80 & 120 \\
\hline
\end{tabular}
\end{center}
The builder needs to work out which houses he should build in order to maximise the total value of the site. He does this using a tree diagram and each "branch" on the tree is terminated when the total area of land on that branch exceeds $12000 \mathrm {~m} ^ { 2 }$.
\begin{enumerate}[label=(\alph*)]
\item \begin{enumerate}[label=(\roman*)]
\item Complete the tree diagram so that each branch is terminated or all choices have been considered.
\item Hence, determine which designs the builder should use and the total value that the site will have when completed.
\end{enumerate}\item Explain how this method could be altered if more than one of each design is allowed.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 Q2 [7]}}