D2 June 2019 Q7

EdexcelOld spec15 marksDynamic Programming

7. A company has purchased a plot of land and has decided to build four holiday homes, A, B, C and D, on the land at the rate of one home per year.

The company expects that the construction costs each year will vary, depending on which houses have already been constructed and which house is currently under construction. The expected construction costs, in thousands of pounds, are shown in the table below.

	Construction cost
Already built	A	B	C	D
Nothing	25	35	35	30
A	–	45	50	55
B	50	–	45	55
C	60	45	–	50
D	65	55	60	–
A and B	–	–	40	35
A and C	–	55	–	30
A and D	–	55	60	–
B and C	45	–	–	50
B and D	65	–	35	–
C and D	55	40	–	–
A and B and C	–	–	–	65
A and B and D	–	–	55	–
A and C and D	–	45	–	–
B and C and D	55	–	–	–

In order to manage annual cash flow, the company needs to choose the order in which it builds the holiday homes so that the greatest expected annual cost of construction is as small as possible.

(a) Write down the type of dynamic programming problem that the company needs to solve. (1)

(b) Use dynamic programming to complete the table in the answer book. (11)

(c) Hence determine the order in which the four holiday homes should be built and the total expected cost of construction. (3)

Scheme	Marks
minimax	B1
	(1)

Mark scheme (b)

Scheme

Marks

Stage	State	Action	Dest.	Value
1	ABC	D	ABCD	65*
	ABD	C	ABCD	55*
	ACD	B	ABCD	45*
	BCD	A	ABCD	55*
2	AB	C	ABC	Max(40, 65) = 65
		D	ABD	Max(35, 55) = 55*
	AC	B	ABC	Max(55, 65) = 65
		D	ACD	Max(30, 45) = 45*
	AD	B	ABD	Max(55, 55) = 55*
		C	ACD	Max(60, 45) = 60
	BC	A	ABC	Max(45, 65) = 65
		D	BCD	Max(50, 55) = 55*
	BD	A	ABD	Max(65, 55) = 65
		C	BCD	Max(35, 55) = 55*
	CD	A	ACD	Max(55, 45) = 55*
		B	BCD	Max(40, 55) = 55*
3	A	B	AB	Max(45, 55) = 55
		C	AC	Max(50, 45) = 50*
		D	AD	Max(55, 55) = 55
	B	A	AB	Max(50, 55) = 55*
		C	BC	Max(45, 55) = 55*
		D	BD	Max(55, 55) = 55*
	C	A	AC	Max(60, 45) = 60
		B	BC	Max(45, 55) = 55*
		D	CD	Max(50, 55) = 55*
	D	A	AD	Max(65, 55) = 65
		B	BD	Max(55, 55) = 55*
		C	CD	Max(60, 55) = 60
4	None	A	A	Max(25, 50) = 50*
		B	B	Max(35, 55) = 55
		C	C	Max(35, 55) = 55
		D	D	Max(30, 55) = 55

M1 A1 (Stage 1)

M1 A1 A1 A1 (Stage 2)

M1 A1ft A1 (Stage 3)

M1 A1 (Stage 4)

(11)

Notes

(The printed mark scheme labels the first M1 A1 “(Stage 2)”; it is for Stage 1, as the notes below confirm. Corrected from the printed mark scheme.)

b1M1: At least three additional rows for the first stage. Value column must contain the values of 55, 45 and 55. Ignore entries in all other columns and condone an error in one value only

b1A1: CAO for the first stage (all three additional rows) – entries in all columns must be correct

b2M1: Second stage – at least 12 rows. Value column must be complete with at least one value correct for each state – ignore entries in all other columns

b2A1: Any two states correct in second stage

b3A1: Any four states correct in second stage

b4A1: Second stage completely correct

b3M1: Third stage – at least 12 rows. Value column must be complete with at least one value correct for each state – ignore entries in all other columns

b5A1ft: Any two states correct in third stage on the ft from second stage

b6A1: Third stage completely correct

b4M1: Fourth stage – at least 4 rows. Value column must be complete with at least one value correct – ignore entries in all other columns

b7A1: Fourth stage completely correct

Special Cases: The number of rows, for each stage, must be as stated above. Fewer rows for any stage leads to M0. In order to score method marks results in each stage must be have been carried forward from the previous stage. The second accuracy mark is awarded if the correct pair of numbers is seen in each of the 12 rows of stage 2, though incorrect manipulation follows.

Minimum Scores at most B0 M1A1 M1A1A0A0 M1A0A0 M1A0 B0M1A0 7/15 marks.

Minimin, Maximum, Maximin Scores at most B0 M1A1 M1A1A0A0 M1A0A0 M1A0 B0M0A0 6/15

Mark scheme (c)

Scheme	Marks
Order is A, C, D, B	DB1
Cost is 25 000 + 50 000 + 30 000 + 45 000 = (£)150 000	M1 A1
	(3)
	15 marks

Notes

c1B1: Correct order – dependent on all M marks awarded in (b)

c1M1: Correct method for calculating cost for their order (condone not working/answer in thousands)

c1A1: CAO