D1 June 2009 Q2

EdexcelOld spec9 marksAlgorithms

The numbers in the list above represent the lengths, in metres, of ten lengths of fabric. They are to be cut from rolls of fabric of length 60m.

(a) Calculate a lower bound for the number of rolls needed. (2)

(b) Use the first-fit bin packing algorithm to determine how these ten lengths can be cut from rolls of length 60m. (4)

Scheme	Marks
\(\dfrac{230}{60} = 3.8\dot{3}\) so 4 needed	M1 A1
	(2)

Mark scheme (b)

Scheme	Marks
Bin 1: 32 17 9 Bin 2: 45 12 Bin 3: 23 28 Bin 4: 38 16 Bin 5: 10	M1 A1 A1 A1
	(4)

Notes

(b) 1M1: Use of first fit. Probably 32, 45 and 17 correctly placed.

1A1: 32, 45, 17, 23, 38 and 28 placed correctly

2A1: 32, 45, 17, 23, 38, 28, 16, 9 placed correctly.

3A1: cao

Special case for (b) misread using first fit decreasing.
Give M1A1 (max)
Bin 1: 45 12
Bin 2: 38 17
Bin 3: 32 28
Bin 4: 23 16 10 9
M1 for placing 45, 38, 32, 28 and 23 correctly
A1 for cao.

Mark scheme (c)

Scheme	Marks
e.g. Bin 1: 32 28 Bin 2: 38 12 10 Bin 3: 45 9 Bin 4: 23 17 16	M1 A1 A1
	(3)
	(9 marks)

Notes

1A1: 2 full bins found

Eg [32+28 and 38+12+10] [23+28+9 and 16+12+32]
[32+28 and 23+16+12+9] [38+12+10 and 23+28+9]

2A1: A 4 bin solution found.