Dynamic programming Decision 2

Papers
A level Paper 4D; AS Paper 2 (option 28)
Level
A level only
Spec
D2.4.1
Booklet
Nothing is given.
Since 2018
13 question parts, 87 marks

Notes, worked examples and practice for this topic are being written by our tutors. The past-paper questions below are ready now: work each one on paper, then open the mark scheme and the examiner's comment.

Past-paper questions

Print this topic as a pack questions first, then the mark schemes

Tap a question to zoom it. Mark scheme and examiner's comment open under each question.
June 2025 · Paper 4D (Decision 2) · Q5(a) 12 marks
5. Anvi makes boats during the winter months. She can make up to five boats each month. If she builds more than three boats in any one month, she must hire an assistant at a cost of £400 for that month. In any month in which boats are made, the overhead costs are £60 for each boat made that month. A maximum of three boats can be held in storage at the end of each month, at a cost of £70 per boat per month. Boats must be delivered at the end of each month. The order schedule for boats is Month November December January February March Number ordered There are no boats in storage at the beginning of November. Anvi plans to have no boats left in storage after the end of the March delivery. (a) Use dynamic programming to determine the production schedule that minimises the costs given above. Complete the working in the table provided in the answer book and state the minimum cost. (12)
June 2025 · Paper 4D (Decision 2) · Q5(b) 1 mark
The assistant asks to work in November, and Anvi agrees. (b) Given that more than three boats are now made in November, state the minimum additional cost of producing all the required boats to the schedule shown above. (1)
June 2024 · Paper 4D (Decision 2) · Q6(a) 9 marks
6. A C F H I S T B E G J Figure 2 The staged, directed network in Figure 2 represents the roads that connect 12 towns, S, A, B, C, D, E, F, G, H, I, J and T. The number on each arc shows the time, in hours, it takes to drive between these towns. Elena plans to drive from S to T. She must arrive at T by 9 pm. (a) By completing the table in the answer book, use dynamic programming to find the latest time that Elena can start her journey from S to arrive at T by 9 pm. (9)
June 2024 · Paper 4D (Decision 2) · Q6(b) 1 mark
(b) Hence write down the route that Elena should take. (1)
June 2023 · Paper 4D (Decision 2) · Q6 13 marks
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. Week Possible countries to visit A or B C, D or E F or G H, I or J Table 1 Table 2 shows the speaker fee, in £100s, Polly would expect to earn in each country. Country A B C E F G H I J Earnings in £100s Table 2 Table 3 shows the cost, in £100s, of travelling between the countries. A B C E F G H I J S A B C E F G Table 3 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)
June 2022 · Paper 4D (Decision 2) · Q6 14 marks
6. Bernie makes garden sheds. He can build up to four sheds each month. If he builds more than two sheds in any one month, he must hire an additional worker at a cost of £250 for that month. In any month in which sheds are made, the overhead costs are £35 for each shed made that month. A maximum of three sheds can be held in storage at the end of any one month, at a cost of £80 per shed per month. Sheds must be delivered at the end of the month. The order schedule for sheds is Month January February March April May Number ordered There are no sheds in storage at the beginning of January and Bernie plans to have no sheds left in storage after the May delivery. Use dynamic programming to determine the production schedule that minimises the costs given above. Complete the working in the table provided in the answer book and state the minimum cost. (14)
Nov 2021 · Paper 4D (Decision 2) · Q6(a) 1 mark
6. E H A B S T F I C G J Figure 3 The staged, directed network in Figure 3 represents a series of roads connecting 12 towns, S, A, B, C, D, E, F, G, H, I, J and T. The number on each arc shows the distance between these towns, in miles. Bradley is planning a four‑day cycle ride from S to T. He plans to leave his home at S. On the first night he will stay at A, B or C, on the second night he will stay at D, E, F or G, on the third night he will stay at H, I or J, and he will arrive at his friend’s house at T on the fourth day. Bradley decides that the maximum distance he will cycle on any one day should be as small as possible. (a) Write down the type of dynamic programming problem that Bradley needs to solve. (1)
Nov 2021 · Paper 4D (Decision 2) · Q6(b) 9 marks
(b) Use dynamic programming to complete the table in the answer book. (9)
Nov 2021 · Paper 4D (Decision 2) · Q6(c) 2 marks
(c) Hence write down the possible routes that Bradley could take. (2)
Oct 2020 · Paper 4D (Decision 2) · Q7(a) 10 marks
7. A manufacturer can export five batches of footwear each year. Each exported batch contains just one type of footwear. The types of footwear are trainers, sandals or high heels. The table below shows the profit, in £1000s, for the number of batches of each type of footwear. Number of batches Trainers Sandals High heels x The total annual profit is to be maximised. (a) Use dynamic programming to determine the two possible values of the maximum total annual profit, giving one of these values in terms of x. (10)
Oct 2020 · Paper 4D (Decision 2) · Q7(b) 2 marks
Given that the maximum total annual profit is £320 000 (b) advise the manufacturer on the possible ways in which the five batches should be allocated. (2)
June 2019 · Paper 4D (Decision 2) · Q3(a) 1 mark
3. A –24 G E H B T S x –24 –17 –25 F I C –30 J Figure 1 In Figure 1 the weight of arc SB is denoted by x where x . 0 (a) Explain why Dijkstra’s algorithm cannot be used on the directed network in Figure 1. (1)
June 2019 · Paper 4D (Decision 2) · Q3(b) 12 marks
It is given that the minimum weight route from S to T passes through B. (b) Use dynamic programming to find (i) the range of possible values of x (ii) the minimum weight route from S to T. (12)

Find an Edexcel Further Maths tutor

Stuck on this? Book a trial lesson with our Further Maths tutor.

Prefer email? Send an enquiry

If you are under 18, please include a parent's contact details. Enquiries go to enquiries@alevelfurthermathstutor.com and are deleted once handled.