Bin packing

Lower bound

Lower bound = total size ÷ bin capacity, rounded up to the next whole number. No solution can use fewer bins. If a packing uses exactly this many bins, it must be optimal.

First fit

Take the items in the order given. Put each one in the first bin (from bin 1) that has room. It is quick but often wasteful, because large items late in the list end up in new bins.

First fit decreasing

Sort the items into decreasing order first (say which sort you used if asked), then apply first fit. It usually does better than first fit, but it is still a heuristic: it is not guaranteed to be optimal.

Full bins

Look for combinations that exactly fill a bin, place those first, then fit the rest. This often finds an optimal packing, but it is hard to do with many items and there may be several answers. Always compare your number of bins with the lower bound.

Worked example

Items 8, 7, 14, 9, 6, 9, 5, 15, 6, 7, 8 must be packed into bins of size 20. Find the lower bound, then use first fit and first fit decreasing.

1. Total = 94; 94 ÷ 20 = 4.7, so the lower bound is 5
2. First fit: bin 1: 8, 7, 5; bin 2: 14, 6; bin 3: 9, 9; bin 4: 15; bin 5: 6, 7; bin 6: 8 (6 bins)
3. First fit decreasing: bin 1: 15, 5; bin 2: 14, 6; bin 3: 9, 9; bin 4: 8, 8; bin 5: 7, 7, 6 (5 bins)

Answer: First fit decreasing uses 5 bins, equal to the lower bound, so it is optimal

Check yourself

1. Items 12, 5, 9, 3, 7, 11, 4, 8, 6 are packed into bins of capacity 16. Find the lower bound for the number of bins.
   Show answer

   5. Total 65; 65 ÷ 16 = 4.0625, which rounds up to 5.

2. Use first fit to pack 12, 5, 9, 3, 7, 11, 4, 8, 6 into bins of capacity 16. How many bins are used?
   Show answer

   5. First fit: bin 1: 12, 3; bin 2: 5, 9; bin 3: 7, 4; bin 4: 11; bin 5: 8, 6.

3. Use first fit decreasing to pack 12, 5, 9, 3, 7, 11, 4, 8, 6 into bins of capacity 16. How many bins are used?
   Show answer

   5. Sorted: 12, 11, 9, 8, 7, 6, 5, 4, 3. Packing: bin 1: 12, 4; bin 2: 11, 5; bin 3: 9, 7; bin 4: 8, 6; bin 5: 3.

4. Using first fit on 12, 5, 9, 3, 7, 11, 4, 8, 6 with bins of capacity 16, what is in bin 2?
   • 12, 3
   • 5, 9, 3
   • 5, 7
   • 5, 9
   Show answer

   5, 9. 12 opens bin 1; 5 does not fit with 12 (17), so opens bin 2; 9 fits bin 2 (14); 3 fits bin 1 (15); nothing later fits bin 2. Full packing: bin 1: 12, 3; bin 2: 5, 9; bin 3: 7, 4; bin 4: 11; bin 5: 8, 6.

5. A packing of items with total size 94 into bins of size 20 uses 5 bins. Which statement is correct?
   • It might not be optimal, because first fit decreasing is a heuristic
   • It is optimal, because 5 is the lower bound
   • It is not optimal, because 94 ÷ 20 is not a whole number
   • Nothing can be said without trying every packing
   Show answer

   It is optimal, because 5 is the lower bound. 94 ÷ 20 = 4.7 rounds up to 5. No packing can use fewer than 5 bins, so 5 bins is optimal.

6. Why is first fit decreasing called a heuristic algorithm?
   • It always gives the optimal solution
   • It uses a random order
   • It needs the items in increasing order
   • It gives a good solution quickly but does not guarantee the optimal one
   Show answer

   It gives a good solution quickly but does not guarantee the optimal one. Heuristic means 'rule of thumb': fast and usually good, but not always optimal.

7. Which of these combinations exactly fills a bin of size 16, using items from 12, 5, 9, 3, 7, 11, 4, 8, 6?
   • 9, 5, 3
   • 12, 4
   • 11, 6
   • 8, 7
   Show answer

   12, 4. 12 + 4 = 16 exactly.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Level in Mathematics specification (issue 3)
• Pearson Edexcel IAL Decision Mathematics 1 scheme of work

Last updated 7 November 2026. Spotted a mistake? Tell us.