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.

Week	1	2	3	4
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	D	E	F	G	H	I	J
Earnings in £100s	47	45	48	47	49	44	45	47	49	48

Table 2

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

	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

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.]

Mark scheme

Scheme

Marks

Stage	State	Action	Dest.	Value
1	H	HS	S	47 – 7 = 40*
	I	IS	S	49 – 8 = 41*
	J	JS	S	48 – 8 = 40*

3.1a

Stage	State	Action	Dest.	Value
2	F	FH	H	44 – 6 + 40 = 78*
		FI	I	44 – 7 + 41 = 78*
		FJ	J	44 – 8 + 40 = 76
	G	GH	H	45 – 7 + 40 = 78
		GI	I	45 – 8 + 41 = 78
		GJ	J	45 – 6 + 40 = 79*

M1
A1
A1

3.1a
1.1b
1.1b

Stage	State	Action	Dest.	Value
3	C	CF	F	48 – 7 + 78 = 119
		CG	G	48 – 5 + 79 = 122*
	D	DF	F	47 – 6 + 78 = 119*
		DG	G	47 – 7 + 79 = 119*
	E	EF	F	49 – 7 + 78 = 120
		EG	G	49 – 6 + 79 = 122*

M1
A1ft
A1

1.1b
1.1b
1.1b

Stage	State	Action	Dest.	Value
4	A	AC	C	47 – 3 + 122 = 166*
		AD	D	47 – 4 + 119 = 162
		AE	E	47 – 5 + 122 = 164
	B	BC	C	45 – 5 + 122 = 162*
		BD	D	45 – 4 + 119 = 160
		BE	E	45 – 6 + 122 = 161

M1
A1ft
A1

1.1b
1.1b
1.1b

Stage	State	Action	Dest.	Value
5	S	SA	A	– 5 + 166 = 161*
		SB	B	– 2 + 162 = 160

1.1b

Optimal schedule is SACGJS
Optimal expected income (£) 16 100

B1
B1

2.2a
3.2a

(13)

(13 marks)

Notes

Condone lack of destination column
Only penalise incorrect result in value – i.e. ignore working values
Penalise absence of state or action column with first two A marks earned only
Penalise empty/errors in stage column with first A mark earned only

For all M marks – must bring optimal results from previous stage into calculation at least once – so from Stage 1 if neither of their 40 or their 41 are used in Stage 2 then M0. Ignore extra rows. Must have correct ingredients (appearance fee, cost) at least once per stage. If no working seen then values in the Value column must be correct to imply these marks. Penalise lack of * only once per question.

B1: CAO (Stage 1)

M1: Second stage completed. At least six rows. Bod if something in each cell

A1: Any one state correct with no extra rows for this state

A1: Both states correct with no extra rows for Stage 2

M1: Third stage completed. At least six rows. Bod if something in each cell

A1ft: Any two states correct – ft their optimal values from Stage 2 (no extra rows)

A1: All three states correct for Stage 3 (no extra rows)

M1: Fourth stage completed. At least six rows. Bod if something in each column

A1ft: Any one state correct - ft their optimal values from Stage 3 (no extra rows)

A1: Both states correct (no extra rows)

A1: Final state correct (no extra rows)

B1: Correct route (dependent on all previous M marks earned). (start and/or finish at S may not be stated)

B1: CAO (dependent on all previous M marks earned) – units not required – but not for 161

Alternative with values added at subsequent Stage

Scheme

Marks

Stage	State	Action	Dest.	Value
1	H	HS	S	– 7 = – 7*
	I	IS	S	– 8 = – 8*
	J	JS	S	– 8 = – 8*

3.1a

Stage	State	Action	Dest.	Value
2	F	FH	H	47 – 6 – 7 = 34*
		FI	I	49 – 7 – 8 = 34*
		FJ	J	48 – 8 – 8 = 32
	G	GH	H	47 – 7 – 7 = 33
		GI	I	49 – 8 – 8 = 33
		GJ	J	48 – 6 – 8 = 34*

M1
A1
A1

3.1a
1.1b
1.1b

Stage	State	Action	Dest.	Value
3	C	CF	F	44 – 7 + 34 = 71
		CG	G	45 – 5 + 34 = 74*
	D	DF	F	44 – 6 + 34 = 72*
		DG	G	45 – 7 + 34 = 72*
	E	EF	F	44 – 7 + 34 = 71
		EG	G	45 – 6 + 34 = 73*

M1
A1ft
A1

1.1b
1.1b
1.1b

Stage	State	Action	Dest.	Value
4	A	AC	C	48 – 3 + 74 = 119*
		AD	D	47 – 4 + 72 = 115
		AE	E	49 – 5 + 73 = 117
	B	BC	C	48 – 5 + 74 = 117*
		BD	D	47 – 4 + 72 = 115
		BE	E	49 – 6 + 73 = 116

M1
A1ft
A1

1.1b
1.1b
1.1b

Stage	State	Action	Dest.	Value
5	S	SA	A	47 – 5 + 119 = 161*
		SB	B	45 – 2 + 117 = 160

1.1b

Optimal schedule is SACGJS
Optimal expected income (£) 16 100

B1
B1

2.2a
3.2a

Notes: as above

Special Case – Working Forwards

Scheme

Marks

Stage	State	Action	Dest.	Value
1	S	SA	A	47 – 5 = 42*
		SB	B	45 – 2 = 43*

Stage	State	Action	Dest.	Value
2	A	AC	C	48 – 3 + 42 = 87*
		AD	D	47 – 4 + 42 = 85
		AE	E	49 – 5 + 42 = 86*
	B	BC	C	48 – 5 + 43 = 86
		BD	D	47 – 4 + 43 = 86*
		BE	E	49 – 6 + 43 = 86*

M1
A1
A0

Stage	State	Action	Dest.	Value
3	C	CF	F	44 – 7 + 87 = 124*
		CG	G	45 – 5 + 87 = 127*
	D	DF	F	44 – 6 + 86 = 124*
		DG	G	45 – 7 + 86 = 124
	E	EF	F	44 – 7 + 86 = 123
		EG	G	45 – 6 + 86 = 125

M1
A1
A0

Stage	State	Action	Dest.	Value
4	F	FH	H	47 – 6 + 124 = 165
		FI	I	49 – 7 + 124 = 166
		FJ	J	48 – 8 + 124 = 164
	G	GH	H	47 – 7 + 127 = 167*
		GI	I	49 – 8 + 127 = 168*
		GJ	J	48 – 6 + 127 = 169*

M1
A0
A0

Stage	State	Action	Dest.	Value
5	H	HS	S	– 7 + 167 = 160*
	I	IS	S	– 8 + 168 = 160*
	J	JS	S	– 8 + 169 = 161*

Optimal schedule is SACGJS
Optimal expected income (£) 16 100

B0
B0

Max: 6/13

Special Case – ignore stars throughout

B1: CAO (Stage 1)

M1: Second stage completed. At least six rows. Bod if something in each cell

A1: Both states correct with no extra rows for Stage 2 then A0

M1: Third stage completed. At least six rows. Bod if something in each cell

A1: Two out of three states with all values correct (no follow through) Then A0

M1: Fourth stage completed. At least six rows. Bod if something in each column. No further marks can be awarded