6 Bob is planning to build four garden sheds, \(A , B , C\) and \(D\), at the rate of one per day. The order in which they are built is a matter of choice, but the costs will vary because some of the materials left over from making one shed can be used for the next one. The expected profits, in pounds, are given in the table below.
| \multirow{2}{*}{Day} | \multirow{2}{*}{Already built} | Expected profit (£) |
| | \(\boldsymbol { A }\) | \(\boldsymbol { B }\) | \(\boldsymbol { C }\) | \(\boldsymbol { D }\) |
| Monday | - | 50 | 65 | 70 | 80 |
| \multirow{4}{*}{Tuesday} | A | - | 72 | 83 | 84 |
| B | 60 | - | 80 | 83 |
| C | 57 | 68 | - | 85 |
| D | 62 | 70 | 81 | - |
| \multirow{6}{*}{Wednesday} | \(\boldsymbol { A }\) and \(\boldsymbol { B }\) | - | - | 84 | 88 |
| \(\boldsymbol { A }\) and \(\boldsymbol { C }\) | - | 71 | - | 82 |
| \(A\) and \(D\) | - | 74 | 83 | - |
| \(\boldsymbol { B }\) and \(\boldsymbol { C }\) | 65 | - | - | 86 |
| \(\boldsymbol { B }\) and \(\boldsymbol { D }\) | 69 | - | 85 | - |
| \(\boldsymbol { C }\) and \(\boldsymbol { D }\) | 66 | 73 | - | - |
| \multirow{4}{*}{Thursday} | \(\boldsymbol { A } , \boldsymbol { B }\) and \(\boldsymbol { C }\) | - | - | - | 90 |
| \(\boldsymbol { A } , \boldsymbol { B }\) and \(\boldsymbol { D }\) | - | - | 87 | - |
| \(A , C\) and \(D\) | - | 76 | - | - |
| \(\boldsymbol { B } , \boldsymbol { C }\) and \(\boldsymbol { D }\) | 70 | - | - | - |
By completing the table of values opposite, or otherwise, use dynamic programming, working backwards from Thursday, to find the building schedule that maximises the total expected profit.
| Stage (Day) | State (Sheds already built) | Action (Shed to build) | Calculation | Profit in pounds |
| Thursday | \(A , B , C\) | D | | 90 |
| \(A , B , D\) | C | | 87 |
| A, C, D | B | | 76 |
| B, C, D | A | | 70 |
| | | | |
| Wednesday | A, B | C | \(84 + 90\) | 174 |
| | D | \(88 + 87\) | 175 |
| A, \(C\) | B | \(71 + 90\) | 161 |
| | D | \(82 + 76\) | 158 |
| A, \(D\) | B | | |
| | C | | |
| \(B , C\) | A | | |
| | D | | |
| \(B , D\) | A | | |
| | C | | |
| \(C , D\) | A | | |
| | B | | |
| | | | |
| Tuesday | A | B | \(72 + 175\) | 247 |
| | C | \(83 + 161\) | 244 |
| | D | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
| Monday | | | | |
| | | | |
| | | | |
| | | | |
\section*{Schedule}
| \cline { 2 - 5 }
\multicolumn{1}{c|}{} | Monday | Tuesday | Wednesday | Thursday |
| Shed to build | | | | |
Turn over
\includegraphics[max width=\textwidth, alt={}]{1aca4e91-d1b3-4a78-8880-e42a4fbf3ddb-18_2486_1714_221_153}