AA10, AA11 - Bin packing algorithms | OCR A-Level Further Mathematics B (MEI)

Bin packing places indivisible items into containers of fixed capacity, usually aiming to use as few containers as possible. You will apply first fit, first fit decreasing and full-bin strategies, justify optimal results using bounds, and count the comparisons made by a precisely stated packing procedure.

First fit keeps the original item order

Could filling one bin perfectly make the eventual packing worse? An attractive local choice can leave awkward items behind. First learn a completely specified rule, so that you can distinguish following an algorithm from improving its answer by inspection.

You already know

A heuristic can give a feasible solution efficiently without guaranteeing an optimum. Exact operation counts depend on the rules, and a counterexample can disprove a general guarantee.

Assume every item has positive size at most the bin capacity $C$ , and items cannot be split. Number bins in the order they are opened.

First fit

Take the items in their given order. For each item, inspect existing bins from bin $1$ upwards, and place it in the first bin with enough remaining capacity. If none fits, open the next bin.

Do not reorder the items or move an earlier item to improve the packing.

“First” refers to the first suitable bin, not the emptiest bin, the fullest bin or the most recently opened one. A bin that failed to fit an earlier large item may fit a later smaller item.

Worked example 1: follow the original order

Question. Apply first fit to items $4,4,6,6$ , in that order, using bins of capacity $10$ .

Plan. Try each existing bin in increasing numerical order, opening a new one only when necessary.

Item	Placement and reason	Bin loads afterwards
$4$	Open bin $1$	$4$
$4$	Bin $1$ has room	$8$
$6$	Bin $1$ has only $2$ spare; open bin $2$	$8,6$
$6$	Bins $1,2$ have only $2,4$ spare; open bin $3$	$8,6,6$

Why this step? The first two items must be placed together by first fit, even if a different arrangement might later be better.

Answer. Bin $1$ : $4,4$ ; bin $2$ : $6$ ; bin $3$ : $6$ . Three bins are used.

Check. All four items appear once, and the loads $8,6,6$ are at most $10$ .

Change only the second item's size from $4$ to $3$ . The original order is still compulsory.

Worked example 2: a smaller item does not change this bin count

Question. Apply first fit to $4,3,6,6$ , with capacity $10$ .

Plan. Update the remaining capacity after each placement and inspect bins from the beginning each time.

Item	Placement and reason	Bin loads afterwards
$4$	Open bin $1$	$4$
$3$	Fits bin $1$	$7$
$6$	Bin $1$ has $3$ spare; open bin $2$	$7,6$
$6$	Neither existing bin fits; open bin $3$	$7,6,6$

Why this step? A smaller second item leaves more space, but still not enough to fit either later item of size $6$ .

Answer. Bins contain $(4,3)$ , $(6)$ , $(6)$ : three bins.

Check. The total size is $19$ , matching loads $7+6+6$ , with no capacity exceeded.

First fit is not in the formula booklet. Its output is determined by the input order and bin capacity, not just the total size.

Watch out

Wrong: put the next item into the last opened bin automatically.

Right: restart the search at bin $1$ for each item and use the first bin that can hold it.

Change the second item once more.

Sort first, then apply first fit

Large items can be harder to place after small items have used the available gaps. First fit decreasing changes the item order before applying the same bin-selection rule.

First fit decreasing

First sort the items into descending order. Then apply first fit to that sorted list, again trying bins in increasing bin-number order for every item.

This remains a heuristic: it is not guaranteed to use the minimum possible number of bins.

Show the sorted list as evidence of the first stage. Sorting does not turn the second stage into a different rule such as choosing the bin with the smallest remaining gap.

Worked example 3: sorting improves the packing

Question. Apply first fit decreasing to $4,4,6,6$ , with capacity $10$ .

Plan. Sort to $6,6,4,4$ , then follow first fit.

Next sorted item	Placement	Bin loads afterwards
$6$	Bin $1$	$6$
$6$	Bin $2$ , because bin $1$ cannot fit it	$6,6$
$4$	Bin $1$ , which has room for exactly $4$	$10,6$
$4$	Bin $2$ , after bin $1$ fails	$10,10$

Why this step? Each smaller item returns to the first suitable earlier bin; it is not automatically paired with the most recent item.

Answer. Two bins, each containing $6,4$ .

Check. The total size is $20$ , and two full capacity- $10$ bins hold all items. First fit on the unsorted list used three bins.

Change only the second original item's size to $3$ , matching the variation in part 1.

Worked example 4: the same two-stage rule

Question. Apply first fit decreasing to $4,3,6,6$ , with capacity $10$ .

Plan. Sort to $6,6,4,3$ , then inspect existing bins in order.

Next sorted item	Placement	Bin loads afterwards
$6$	Open bin $1$	$6$
$6$	Open bin $2$	$6,6$
$4$	Fill bin $1$	$10,6$
$3$	Bin $1$ fails; use bin $2$	$10,9$

Why this step? The sorted order changes the packing, while the first-fit search order remains unchanged.

Answer. Bin $1$ : $6,4$ ; bin $2$ : $6,3$ .

Check. Loads $10,9$ sum to $19$ and stay within capacity.

The rule is not in the formula booklet. A good result on these examples is not a proof that decreasing order always finds an optimum.

Watch out

Wrong: call any descending-order packing first fit decreasing.

Right: sorting is only the first stage; the actual placements must still use the first suitable bin.

Repeat with the next variation.

A full-bin strategy needs a separate optimality argument

A full-bin strategy looks for combinations that fill a bin exactly, or make good use of its space, then considers what remains. It can improve a first-fit result, but is a strategy with choices rather than one prescribed ordering rule. Filling one bin does not guarantee a globally optimal packing.

Capacity lower bound

If total item size is $S$ and bin capacity is $C>0$ , any feasible packing uses at least

L=\left\lceil\frac SC\right\rceil

bins. The ceiling means the smallest integer at least $S/C$ . A feasible packing using $L$ bins is optimal.

Not in the formula booklet: learn it.

A lower bound need not be attainable. For example, three items of size $6$ , with capacity $10$ , have total $18$ and capacity bound $2$ , but no two can share a bin. They need three bins. The contents matter as well as the total.

Worked example 5: improving both first-fit heuristics

Question. Items have sizes $6,5,3,2,2,2$ , with capacity $10$ . Find an optimal packing using a full-bin strategy, and explain what this shows about first fit decreasing.

Plan. Look for exact totals of $10$ , then compare the resulting bin count with a capacity lower bound.

6+2+2=10,\qquad 5+3+2=10

These groups use every item once, so they form two full bins. Also

S=20,\qquad L=\left\lceil\frac{20}{10}\right\rceil=2

First fit decreasing processes the already decreasing list and instead gives $(6,3)$ , $(5,2,2)$ , $(2)$ , using three bins.

Why this step? A feasible two-bin construction reaches the lower bound, proving its optimality rather than merely improving one attempted packing.

Answer. Bins $(6,2,2)$ and $(5,3,2)$ are optimal. First fit decreasing uses three bins here, so it does not guarantee an optimum.

Check. Both bin totals equal $10$ , and the three items of size $2$ are all accounted for.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account

Last Accessed

Core Pure

Mechanics (Major and Minor)

Statistics (Major and Minor)

Modelling with Algorithms

Numerical Methods

Extra Pure

Further Pure with Technology

AA10, AA11 - Bin packing algorithms

First fit keeps the original item order

Sort first, then apply first fit

A full-bin strategy needs a separate optimality argument

Continue this lesson.

Learn faster with Nova