D1 June 2010 Q3

EdexcelOld spec9 marksAlgorithms

41 28 42 31 36 32 29

The numbers in the list represent the weights, in kilograms, of seven statues. They are to be transported in crates that will each hold a maximum weight of 60 kilograms.

(a) Calculate a lower bound for the number of crates that will be needed to transport the statues. (2)

(b) Use the first-fit bin packing algorithm to allocate the statues to the crates. (3)

(d) Explain why it is not possible to transport the statues using fewer crates than the number needed for part (c). (2)

Mark scheme (a)

Scheme	Marks
e.g. total weight is 239, lower bound is \(\dfrac{239}{60} = 3.98\) so 4 bins.	M1 A1
	(2)

Notes

1M1: Any correct statement, must involve calculation

1A1: cao (accept 4 for both marks)

Mark scheme (b)

Scheme	Marks
Bin 1 : 41 Bin 4 : 36 Bin 2 : 28 + 31 Bin 5 : 32 Bin 3 : 42 Bin 6: 29	M1 A1 A1
	(3)

Notes

1M1: Bins 1 and 2 correct and at least 6 values put in bins

1A1: Bins 1,2,3 and 4 correct.

2A1: All correct

Misread in (b) First Fit Decreasing

Bin 1: 42 Bin 2: 41 Bin 3: 36 Bin 4: 32 28 Bin 5: 31 29
(Remove up to two A marks if earned – so M1 max in (b) if first 4 bins correct.)

Scheme	Marks
Full Bins : 28 + 32 31 + 29 The other 3 items (42, 41, 36) require 3 separate bins	M1 A1
	(2)

Mark scheme (d)

Scheme	Marks
There are 5 items over 30. No two of these 5 can be paired in a bin, so at least 5 bins will be required.	B2, 1, 0
	(2)
	(9 marks)

Notes

1B1: Correct argument may be imprecise or muddled (bod gets B1)

2B1: A good, clear, correct argument.(They have answered the question ‘why?’)