Joan sells ice cream. She needs to decide which three shows to visit over a three-week period in the summer. She starts the three-week period at home and finishes at home. She will spend one week at each of the three shows she chooses travelling directly from one show to the next.

Table 1 gives the week in which each show is held. Table 2 gives the expected profits from visiting each show. Table 3 gives the cost of travel between shows.

\textbf{Table 1}
\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
Week & 1 & 2 & 3 \\
\hline
Shows & A, B, C & D, E & F, G, H \\
\hline
\end{tabular}
\end{center}

\textbf{Table 2}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
Show & $A$ & $B$ & $C$ & $D$ & $E$ & $F$ & $G$ & $H$ \\
\hline
Expected Profit (£) & 900 & 800 & 1000 & 1500 & 1300 & 500 & 700 & 600 \\
\hline
\end{tabular}
\end{center}

\textbf{Table 3}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
Travel costs (£) & $A$ & $B$ & $C$ & $D$ & $E$ & $F$ & $G$ & $H$ \\
\hline
Home & 70 & 80 & 150 & & & 80 & 90 & 70 \\
\hline
$A$ & & & & 180 & 150 & & & \\
\hline
$B$ & & & & 140 & 120 & & & \\
\hline
$C$ & & & & 200 & 210 & & & \\
\hline
$D$ & & & & & & 200 & 160 & 120 \\
\hline
$E$ & & & & & & 170 & 100 & 110 \\
\hline
\end{tabular}
\end{center}

It is decided to use dynamic programming to find a schedule that maximises the total expected profit, taking into account the travel costs.

\begin{enumerate}[label=(\alph*)]
\item Define suitable stage, state and action variables. [3]
\item Determine the schedule that maximises the total profit. Show your working in a table. [12]
\item Advise Joan on the shows that she should visit and state her total expected profit. [3]
\end{enumerate}
(Total 18 marks)

\hfill \mbox{\textit{Edexcel D2 2004 Q6 [18]}}