D2 June 2014 (R) Q7

EdexcelOld spec13 marksDynamic Programming

7. Susie has hired a team of four workers who can make three types of toy. The total number of toys the team can produce will depend on which toys they make, and on how many workers are assigned to make each type of toy.

The table shows how many of each toy would be made if different numbers of workers were assigned to make them. Each worker is to be assigned to make just one type of toy and all four workers are to be assigned. Susie wishes to maximise the total number of toys produced.


		1	2	3	4
TOYS	Bicycle	80	170	260	350
	Dolls House	95	165	245	335
	Train Set	100	180	260	340

(a) Use dynamic programming to determine the allocation of workers which maximises the total number of toys made. You should show your working in the table provided in the answer book. (12)

(b) State the maximum total number of toys produced by this team. (1)

Mark scheme (a)

E.g.

Stage	State	Action	Dest	Value	Marks
Bicycle	4	4	0	350	1M1 1A1 (2)
	3	3	0	260
	2	2	0	170
	1	1	0	80
	(0	0	0	0)
Dolls	4	0	4	0 + 350 = 350
house		1	3	95 + 260 = 355*	2M1 2A1 3A1 (3)
		2	2	165 + 170 = 335	States 4 + 3
		3	1	245 + 80 = 325
		4	0	335 + 0 = 335
	3	0	3	0 + 260 = 260
		1	2	95 + 170 = 265*
		2	1	165 + 80 = 245
		3	0	245 + 0 = 245
	2	0	2	0 + 170 = 170	3M1 4A1 5A1 (3)
		1	1	95 + 80 = 175*
		2	0	165 + 0 = 165	States 2 + 1
	1	0	1	0 + 80 = 80
		1	0	95 + 0 = 95*
	(0	0	0	0 + 0 = 0)
Train	4	0	4	0 + 355 = 355
set		1	3	100 + 265 = 365*	4M1 6A1ft 7A1 (3)
		2	2	180 + 175 = 355
		3	1	260 + 95 = 355
		4	0	340 + 0 = 340

Scheme

Marks

Toy	Bicycle	Dolls House	Train Set
Number of workers	2	1	1

1B1

(1)

Notes

ALL M marks - Must bring earlier optimal results into calculations. Ignore extra rows. Must have right ‘ingredients’ (– number of workers) at least once per stage.
Penalise inconsistency/errors with the state/destination columns with the first two A marks earned only.
Penalise empty/errors in stage column with first A mark earned only.

a1M1: First stage (Bicycle) completed – bod something in each cell. Must have columns for stage, state, value and one of either action or destination.

a1A1: CAO condone missing * here. Condone missing zero row.

a2M1: Second stage (Dolls house) completed for at least states 4 and 3. Bod something in each cell.

a2A1: Any one of these states correct. No missing rows. (Penalise * errors only once in the question).

a3A1: CAO both states 4 and 3 correct. No missing rows. (Penalise * errors only once in the question).

a3M1: Second stage (Dolls house) fully completed, condone missing zero row. Bod something in each cell.

a4A1: States 2 and 1 correct. No missing rows. (Penalise * errors only once in the question).

a5A1: CAO for stage 2. No missing rows. (Penalise * errors only once in the question).

a4M1: Third stage (Train set) completed. Bod something in each cell.

a6A1ft: Any three rows of third stage correct. Ft on * values only. No missing rows. (Penalise * errors only once in the question).

a7A1: CAO for the third stage. No missing rows. (Penalise * errors only once in the question).

a1B1: CAO. Must have attempted algorithm, getting all previous M marks.