Robinson Tuition
AS Decision Mathematics 1 · Edexcel 8FM0 · free Further Maths worksheet

Bin packing

Lower bound for the number of bins, first-fit, first-fit decreasing and full-bin packing, comparing methods and deciding whether a packing is optimal, problems in context.

12 original questions, 71 marks. Type your answers below for an instant mark and a score (algebra in any equivalent form, e.g. 2sqrt(3) or 2√3), or print the worksheet, mark it with the answers sheet, and use the solutions to see every step written out by hand.

Worksheet PDFWorked solutions PDFAnswers PDF

The questions

1

Boxes with the following masses, in kilograms, are to be loaded onto trolleys. Each trolley can carry at most 20 kg.

8 11 6 14 3 9 12 5 7

Calculate a lower bound for the number of trolleys needed. You must make your method clear.

2 marks
Show answer
4
2

Use the first-fit bin packing algorithm to pack the following numbers into bins of size 25

7 13 9 4 15 6 11 8 2

3 marks
Show answer
Bin 1: 7, 13, 4; Bin 2: 9, 15; Bin 3: 6, 11, 8; Bin 4: 2
3

Use the first-fit decreasing bin packing algorithm to pack the following numbers into bins of size 30

12 5 18 9 14 7 16 3

3 marks
Show answer
Bin 1: 18, 12; Bin 2: 16, 14; Bin 3: 9, 7, 5, 3
4

A dressmaker needs these lengths of ribbon, in metres. Ribbon is sold on reels of 5 m and each length must be cut from a single reel.

2.4 1.7 3.1 0.9 2.6 1.3 3.5 2.2 1.8

  1. Calculate a lower bound for the number of reels needed.
  2. Use the first-fit bin packing algorithm to show how the lengths could be cut from the reels.
  3. Use the first-fit decreasing algorithm to show how the lengths could be cut from the reels.
  4. Explain whether your answer to part (c) is optimal.
7 marks
Show answer
a) 4 b) Bin 1: 2.4, 1.7, 0.9; Bin 2: 3.1, 1.3; Bin 3: 2.6, 2.2; Bin 4: 3.5; Bin 5: 1.8 c) Bin 1: 3.5, 1.3; Bin 2: 3.1, 1.8; Bin 3: 2.6, 2.4; Bin 4: 2.2, 1.7, 0.9 d) optimal: 4 reels = lower bound
5

The numbers below are to be packed into bins of size 20

11 4 7 9 13 6 8 2 10 5

  1. Use full-bin packing to pack the numbers into bins.
  2. Explain why your packing is optimal.
5 marks
Show answer
a) 11 + 9, 13 + 7, 10 + 6 + 4 full; 8, 2, 5 in a fourth bin b) lower bound 4 = number of bins used
6

The eight distinct integers 14, 9, x, 17, 6, 11, 8, 5 are packed, in that order, into bins of size 30 using the first-fit algorithm. The result is

Bin 1: 14  9  6
Bin 2: x  17
Bin 3: 11  8  5

  1. Explain why 8 < x ≤ 13
  2. Hence write down the possible values of x.
  3. Given that x = 12, use the first-fit decreasing algorithm to pack the numbers into bins of size 30, and state whether your packing is optimal.
7 marks
Show answer
a) x + 23 > 30, x + 17 ≤ 30, x + 22 > 30 b) 10, 12, 13 c) Bin 1: 17, 12; Bin 2: 14, 11, 5; Bin 3: 9, 8, 6; optimal (lower bound 3)
7

The numbers 18, 7, 25, 12, 9, 20, 14, 6 are packed, in that order, into bins of size n, where n is an integer, using the first-fit algorithm. The result is

Bin 1: 18  7  12
Bin 2: 25  9
Bin 3: 20  14
Bin 4: 6

Find the possible values of n. You must give reasons for your answer.

4 marks
Show answer
37, 38 or 39
8

The eight distinct integers below are to be packed into bins of size 24

10  14  x  16  8  13  11  3

It is known that x is the largest number in the list and that x < 24

  1. Explain why the numbers cannot be packed into 3 bins.
  2. Given that the numbers can be packed into 4 bins, find the range of possible values of x.
  3. Taking the largest possible value of x, use the first-fit algorithm to pack the numbers, and comment on the result.
7 marks
Show answer
a) 75 + x ≥ 92 > 72 b) 17 ≤ x ≤ 21 c) Bin 1: 10, 14; Bin 2: 21, 3; Bin 3: 16, 8; Bin 4: 13, 11; 4 bins, optimal
9

A carpenter needs to cut shelves of the following lengths, in metres, from planks that are 3.6 m long. Each shelf must be cut from a single plank.

1.2 0.8 2.1 1.5 0.6 1.9 1.1 0.7 1.4 2.4

  1. Calculate a lower bound for the number of planks needed.
  2. Use the first-fit bin packing algorithm to allocate the shelves to planks.
  3. Use the first-fit decreasing algorithm to allocate the shelves to planks.
  4. State which allocation the carpenter should use, and whether it is optimal. Give a reason.
8 marks
Show answer
a) 4 b) Bin 1: 1.2, 0.8, 1.5; Bin 2: 2.1, 0.6, 0.7; Bin 3: 1.9, 1.1; Bin 4: 1.4; Bin 5: 2.4 c) Bin 1: 2.4, 1.2; Bin 2: 2.1, 1.5; Bin 3: 1.9, 1.4; Bin 4: 1.1, 0.8, 0.7, 0.6 d) 4 planks = lower bound, optimal
10

A courier has ten parcels to deliver. Their masses, in kilograms, are

320 150 410 280 90 230 360 175 260 125

Each van can carry at most 900 kg.

  1. Calculate a lower bound for the number of vans needed.
  2. Use the first-fit decreasing algorithm to allocate the parcels to vans.
  3. Explain why your allocation is optimal.
  4. A late parcel arrives. Using your allocation, find the greatest mass it could have so that no extra van is needed.
8 marks
Show answer
a) 3 b) Bin 1: 410, 360, 125; Bin 2: 320, 280, 260; Bin 3: 230, 175, 150, 90 c) 3 vans = lower bound 3 d) 255 kg
11

The numbers below are to be packed into bins of size 40

23 8 31 17 26 12 35 5 19 14

  1. Use a quick sort to put the numbers into descending order. You should show the result of each pass and identify your pivots clearly.
  2. Use the first-fit decreasing algorithm to pack the numbers into bins of size 40
  3. Calculate a lower bound for the number of bins and determine whether your packing is optimal.
9 marks
Show answer
a) 35 31 26 23 19 17 14 12 8 5 b) Bin 1: 35, 5; Bin 2: 31, 8; Bin 3: 26, 14; Bin 4: 23, 17; Bin 5: 19, 12 c) lower bound 5; optimal
12

A local radio station has ten adverts to broadcast. Their lengths, in seconds, are

75 35 55 75 15 50 85 50 60 40

The adverts are to be placed in advert breaks, each of which lasts at most 3 minutes.

  1. Use the first-fit decreasing algorithm to allocate the adverts to breaks.
  2. Calculate a lower bound for the number of breaks.
  3. Use full-bin packing to show that the adverts can be broadcast in fewer breaks than your answer to part (a).
  4. Explain what this shows about the first-fit decreasing algorithm.
8 marks
Show answer
a) Bin 1: 85, 75, 15; Bin 2: 75, 60, 40; Bin 3: 55, 50, 50; Bin 4: 35 b) 3 c) 85 + 60 + 35, 75 + 55 + 50, 75 + 50 + 40 + 15 d) heuristic: not guaranteed optimal

Your score

Answer the questions above and your score appears here.

Every question here is original and written by Robinson Tuition. It follows the Edexcel AS Further Mathematics specification and suits AQA and OCR Further Maths too; this is not an exam-board paper.

All AS Decision Mathematics 1 topics