Total 30, capacity 10
lower bound ⌈30/10⌉ = 3
At least 3 bins.
The number of bins of capacity needed for items of total size is at least . This lower bound is often, but not always, achievable.
This page is easier if you are comfortable with:
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).
The total size divided by the bin capacity gives the fewest bins any packing could use.
Total 36 over capacity 10 needs at least 4 bins, and 4 suffice.
These examples are worked by hand, step by step, so you can compare your own working.
Find the lower bound for sizes 4, 8, 1, 4, 2, 1, 7, 3, 1, 5 with capacity 10.
Find the lower bound for sizes 5, 5, 5, 3, 3 with capacity 10.
Find the bound for sizes 6, 6, 6 with capacity 10 (3 bins are actually needed).
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
lower bound ⌈30/10⌉ = 3
At least 3 bins.
⌈3.7⌉ = 4
Round up.
may use more than the bound
Heuristic.
each needs its own bin
Stronger bound.
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.
Items total 30 with bins of capacity 10. Find the lower bound.
Items total 37 with capacity 10.
Sizes 6, 5, 4, 7, 3, 5 with capacity 10. Find the bound.
Sizes 6, 7, 8, 6, 3 with capacity 10: four items exceed 5. Bound?
⌊3.7⌋ = 3 ✗
⌈3.7⌉ = 4 ✓
Round up for a bound.
bound = optimum ✗
optimum ≥ bound ✓
It may need more bins.
forgetting an item ✗
sum all items ✓
Add carefully.
S/n ✗
S/C ✓
Use capacity.
Try each one on paper, then open the answer. Use the solver above to see the full working.
5
2
4
20
2
4
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
⌈total size ÷ capacity⌉.
You cannot use part of a bin.
Not always.
A greedy packing heuristic.
More in Discrete maths and number theory and the formula sheets.