Dynamic programmingEdexcel A-Level Further Maths: Mind map

Exam questions on Dynamic programming

1. A network of roads joins S to T through junctions A, B, C and D. The roads and their lengths, in km, are: SA 5, SB 3, AC 4, AD 7, BC 6, BD 2, CT 5 and DT 6. Dynamic programming is used to find the shortest route from S to T, working backwards from T. Stage 1 is the final step into T (from C or D), stage 2 is the step from A or B, and stage 3 is the step from S. The state is the vertex and the action is the next vertex.
   Given that the shortest distance from A to T is $9$ km, complete the dynamic programming to find the shortest route from S to T and its length.2 marks
2. Messages are sent from S to T through routers A, B, C and D. The speed of a link is its capacity in Mbps, and the speed of a route is the speed of its slowest link. The links and capacities are: SA 8, SB 6, AC 4, AD 7, BC 9, BD 4, CT 6 and DT 5. The manager wants a route whose speed is as large as possible and uses dynamic programming, working backwards from T.
   Given that the best speed from A to T is $5$ Mbps, complete the dynamic programming to find the best route from S to T and its speed.2 marks
3. A firm has 5 engineers to share between three projects, and all five must be used. The profit, in £ thousand, when a project is given 0, 1, 2, 3, 4 or 5 engineers is: Project 1: 0, 7, 9, 10, 11, 17. Project 2: 0, 6, 9, 13, 15, 16. Project 3: 0, 1, 7, 14, 18, 25. The firm uses dynamic programming to maximise the total profit. Stage 1 is Project 3, stage 2 is Projects 2 and 3 together, and stage 3 is all three projects. The state is the number of engineers available at that stage and the action is the number given to the project being considered.
   Find the value of the best allocation of 4 engineers to Projects 2 and 3 together, and say how many go to Project 2, showing the options you compare.3 marks