4. This question should be answered on the sheet provided.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{4e50371b-0c1c-4b4e-b21d-60858ae160df-3_771_1479_1178_237}
\captionsetup{labelformat=empty}
\caption{Fig. 2}
\end{figure}
A salesman is planning a four-day trip beginning at home and ending at town \(I\). He will spend the first night in town \(A , B\) or \(C\), the second night in town \(D , E\) or \(F\) and the third night in town \(G\) or \(H\). The network in Figure 2 shows the expected net profit, in tens of pounds, that he will gain on each day according to the route he chooses.
Use dynamic programming to find the route which should maximise the salesman’s net profit. State the expected profit from using this route.
(10 marks)