6. Polly is a motivational speaker who is planning her engagements for the next four weeks.
Polly will
- visit four different countries in these four weeks
- visit just one country each week
- leave from her home, S , and return there only after visiting the four countries
- travel directly from one country to the next
Polly wishes to determine a schedule of four countries to visit.
Table 1 shows the countries Polly could visit each week.
\begin{table}[h]
| Week | 1 | 2 | 3 | 4 |
| Possible countries to visit | A or B | C, D or E | F or G | H, I or J |
\captionsetup{labelformat=empty}
\caption{Table 1}
\end{table}
Table 2 shows the speaker fee, in \(\pounds 100\) s, Polly would expect to earn in each country.
\begin{table}[h]
| Country | A | B | C | D | E | F | G | H | I | J |
| Earnings in \(\boldsymbol { \pounds } \mathbf { 1 0 0 s }\) | 47 | 45 | 48 | 47 | 49 | 44 | 45 | 47 | 49 | 48 |
\captionsetup{labelformat=empty}
\caption{Table 2}
\end{table}
Table 3 shows the cost, in \(\pounds 100\) s, of travelling between the countries.
\begin{table}[h]
| A | B | C | D | E | F | G | H | I | J |
| S | 5 | 2 | | | | | | 7 | 8 | 8 |
| A | | | 3 | 4 | 5 | | | | | |
| B | | | 5 | 4 | 6 | | | | | |
| C | | | | | | 7 | 5 | | | |
| D | | | | | | 6 | 7 | | | |
| E | | | | | | 7 | 6 | | | |
| F | | | | | | | | 6 | 7 | 8 |
| G | | | | | | | | 7 | 8 | 6 |
\captionsetup{labelformat=empty}
\caption{Table 3}
\end{table}
Polly's expected income is the value of the speaker fee minus the cost of travel.
She wants to find a schedule that maximises her total expected income for the four weeks.
Use dynamic programming to determine the optimal schedule. Complete the table provided in the answer book and state the maximum expected income.
(13)