Bin Packing Lower Bound Explained with Worked Examples

The number of bins of capacity needed for items of total size is at least . This lower bound is often, but not always, achievable.

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

What Bin packing lower bound means

Items of sizes 4, 8, 1, 4, 2, 1, 7, 3, 1, 5 total 36; with bins of capacity 10 the bound is bins, and four bins suffice (8+2, 7+3, 5+4+1 and 4+1+1). Sizes 5, 5, 5, 3, 3 total 21: the bound is . Sizes 6, 6, 6 with capacity 10 total 18, bound , but no two sixes fit together, so 3 bins are needed: the bound is not always tight.

The bound is the ceiling of the total divided by the capacity: no packing can do better than perfectly full bins (the pigeonhole principle gives the same kind of argument). Heuristics such as first-fit decreasing give a packing to compare with this bound; if they match, the packing is optimal. Finding the true optimum is a hard problem (NP-hard).

The same lower-bound idea (total demand over capacity) appears in scheduling and in linear programming relaxations (linear programming duality); other decision-maths bounds are those for the travelling salesperson problem (travelling salesperson bounds) and critical paths (critical path float).

What is it used for?

The total size divided by the bin capacity gives the fewest bins any packing could use.

How to use bin packing lower bound

  1. Add up all item sizes.
  2. Divide by the bin capacity.
  3. Round up to the next integer.
  4. Compare with the number of bins used by a heuristic.

Graph

Bin loads of a packing of ten items into 4 bins of capacity 108+27+35+4+14+1+100.511.522.533.544.55024681012Bin loads of a packing of ten items into 4 bins of capacity 10binyGraph with x from 0 to 5 and y from 0 to 12. Shows bars (4); point 8+2 at (1, 10); point 7+3 at (2, 10); point 5+4+1 at (3, 10); point 4+1+1 at (4, 6).

Total 36 over capacity 10 needs at least 4 bins, and 4 suffice.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: ten items

Find the lower bound for sizes 4, 8, 1, 4, 2, 1, 7, 3, 1, 5 with capacity 10.

Worked example
Answer
44
  1. Total
  2. Bound

Example 2: five items

Find the lower bound for sizes 5, 5, 5, 3, 3 with capacity 10.

Worked example
Answer
33
  1. Total
  2. Bound

Example 3: a bound that is not tight

Find the bound for sizes 6, 6, 6 with capacity 10 (3 bins are actually needed).

Worked example
Answer
22
  1. Total
  2. Bound

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

Total 30, capacity 10

lower bound ⌈30/10⌉ = 3

At least 3 bins.

Total 37, capacity 10

⌈3.7⌉ = 4

Round up.

First-fit

may use more than the bound

Heuristic.

Items > half capacity

each needs its own bin

Stronger bound.

Word problems

The lower bound on the number of bins of capacity C for items of total size S is ⌈S/C⌉. Any packing needs at least this many bins.

Exact fit

Items total 30 with bins of capacity 10. Find the lower bound.

  1. 30 ÷ 103
  2. Check: ✓3.

Round up

Items total 37 with capacity 10.

  1. 3.7
  2. Round up4
  3. Check: ✓4.

Items list Higher

Sizes 6, 5, 4, 7, 3, 5 with capacity 10. Find the bound.

  1. Total30
  2. ⌈30/10⌉3
  3. Check: ✓3.

Big items Higher

Sizes 6, 7, 8, 6, 3 with capacity 10: four items exceed 5. Bound?

  1. Total 30 → 3
  2. Four items > 5 → 4
  3. Check: at least 4 ✓4.

Common mistakes

Rounding down

⌊3.7⌋ = 3 ✗

⌈3.7⌉ = 4 ✓

Round up for a bound.

Treating the bound as the answer

bound = optimum ✗

optimum ≥ bound ✓

It may need more bins.

Wrong total

forgetting an item ✗

sum all items ✓

Add carefully.

Dividing by item count

S/n ✗

S/C ✓

Use capacity.

Exam tips

  1. ⌈S/C⌉.
  2. Round up.
  3. Bound ≤ optimum.
  4. Big items need own bins.
  5. Heuristics may use more.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. Total 45, capacity 10 Foundation

5

2. Total 20, capacity 10 Foundation

2

3. Total 61, capacity 20 Foundation

4

4. Items 4, 8, 1, 4, 2, 1: total Higher

20

5. Bound for those items, capacity 10 Higher

2

6. Total 99, capacity 25 Higher

4

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Bin packing
Fitting items into the fewest bins.
Lower bound
The least possible number.
Ceiling
Round up.
First-fit
Put each item in the first bin it fits.
Capacity
Size of each bin.
Optimal packing
Uses the fewest bins.

Frequently asked questions

What is the bin-packing lower bound?

⌈total size ÷ capacity⌉.

Why round up?

You cannot use part of a bin.

Is the bound always achievable?

Not always.

What is first-fit?

A greedy packing heuristic.

Which page covers critical paths?

critical path.

Which page covers Hall’s theorem?

Hall’s marriage theorem.

More in Discrete maths and number theory and the formula sheets.