Dynamic Programming

Edexcel

A2 June 2025 Q5

EdexcelCurrent spec13 marksDynamic Programming

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

MonthNovemberDecemberJanuaryFebruaryMarch
Number ordered25643

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)

[The table in the answer book begins as follows.]

StageStateActionDestinationValue
March300210 = 210*
210140 + 60 = 200*
12070 + 120 = 190*
030180 = 180*

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)

A2 June 2024 Q6

EdexcelCurrent spec10 marksDynamic Programming

6.

Figure 2: staged directed network from S to T with arcs SA 3, SB 2, AC 4, AE 5, BC 4, BD 7, BE 4, CF 3, CG 4, DF 3, DG 1, EG 2, FH 5, FI 4, FJ 6, GH 5, GI 3, HT 2, IT 3, JT 4
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)

[The table in the answer book has columns headed Stage, State, Action, Destination and Value.]

(b) Hence write down the route that Elena should take. (1)

A2 June 2023 Q6

EdexcelCurrent spec13 marksDynamic Programming

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.

Week1234
Possible countries to visitA or BC, D or EF or GH, I or J

Table 1

Table 2 shows the speaker fee, in £100s, Polly would expect to earn in each country.

CountryABCDEFGHIJ
Earnings in £100s47454847494445474948

Table 2

Table 3 shows the cost, in £100s, of travelling between the countries.

ABCDEFGHIJ
S52788
A345
B546
C75
D67
E76
F678
G786

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)

[The table in the answer book has columns headed Stage, State, Action, Destination and Value.]

A2 June 2022 Q6

EdexcelCurrent spec14 marksDynamic Programming

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

MonthJanuaryFebruaryMarchAprilMay
Number ordered13352

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 below and state the minimum cost. (14)

StageStateActionDestinationValue
May200160 = 160*
11080 + 35 = 115*
02070 = 70*
MonthJanuaryFebruaryMarchAprilMay
Number made

Minimum cost:

A2 October 2021 Q6

EdexcelCurrent spec12 marksDynamic Programming

6.

Figure 3: staged directed network from S to T with arcs SA 52, SB 48, SC 50, AD 53, AE 52, AF 53, BE 51, BF 50, BG 46, CE 50, CG 47, DH 49, DI 50, EH 51, EJ 46, FH 51, FI 52, FJ 50, GI 53, GJ 51, HT 47, IT 48, JT 49
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)
(b) Use dynamic programming to complete the table below. (9)
StageStateActionDestinationValue
(c) Hence write down the possible routes that Bradley could take. (2)

A2 October 2020 Q7

EdexcelCurrent spec12 marksDynamic Programming

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 batches012345
Trainers05090170225295
Sandals070110165245300
High heels075115\(x\)235305

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)

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)

A2 June 2019 Q3

EdexcelCurrent spec13 marksDynamic Programming

3.

Figure 1: staged directed network from S to T with arcs SA 13, SB x, SC 24, AD 32, AE 29, BD 20, BE 19, BF −17, CF 13, DG −24, DH 18, EH 24, EI 27, FG −25, FI 14, FJ −30, GT 28, HT 19, IT −24, JT 17
Figure 1

In Figure 1 the weight of arc SB is denoted by \(x\) where \(x \geqslant 0\)

(a) Explain why Dijkstra’s algorithm cannot be used on the directed network in Figure 1. (1)

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)