D1 1.2 - Bin packing algorithms
Bin packing places items into containers of fixed capacity without splitting an item. You will apply first-fit and first-fit decreasing, distinguish a heuristic packing from an optimum, and infer a capacity from the placements an algorithm makes.
First-fit in the original item order
Can rearranging four items reduce the number of bins from three to two? With capacity , first-fit on uses three bins. A different order can use two. The input order is part of the algorithm, not an incidental detail.
You already know
A sorting algorithm changes an item's position in a list; an algorithm trace must retain every original item exactly once. In bin packing, equal-sized items are still separate items and must all be placed.
We now keep the input order fixed and decide where each item goes. The search always begins with the earliest bin.
First-fit bin packing
Take items in their given order. For each item, examine existing bins from Bin 1 onwards and place it in the first bin with enough remaining capacity. If no existing bin can hold it, open the next bin. Return to Bin 1 for the next item.
Each item is indivisible, and each size must be positive and no greater than the capacity. An item exactly equal to the remaining space fits. First-fit is not “put it in the most recently opened bin” or “choose the tightest-fitting bin”.
Worked example 1: returning to an earlier bin
Question. Use first-fit to pack into bins of capacity .
Plan. Take the list in order, checking Bin 1 first for every item.
| Item | Placement | Reason |
|---|---|---|
| Bin 1 | First bin opened | |
| Bin 2 | ||
| Bin 1 | ||
| Bin 2 | Bin 1 full; in Bin 2 |
Why return to Bin 1 for the ? First-fit restarts its search at the first bin, so an earlier space remains available.
Answer. Bin 1: . Bin 2: .
Check. Both totals are , and every item has been placed exactly once.
Worked example 2 changes only the bin capacity, from to . The earlier exact fit no longer works.
Worked example 2: a smaller capacity
Question. Use first-fit to pack into bins of capacity .
Plan. Keep the original item order and recheck every placement against the new capacity.
| Item | Placement | Reason |
|---|---|---|
| Bin 1 | Fits | |
| Bin 2 | ||
| Bin 2 | Bin 1 cannot hold it; | |
| Bin 3 | Neither existing bin can hold it |
Why does the move? Bin 1 has only units free, so the algorithm must continue checking later bins.
Answer. Bin 1: . Bin 2: . Bin 3: .
Check. Totals are all at most ; the packed total is .
Write the contents of each bin, rather than only its cumulative total. The contents show whether an item was omitted, duplicated or placed out of sequence.
Watch out
Wrong: put an item into the last bin that has room. Right: choose the first bin that has room, restarting at Bin 1 for every item.
Increase the capacity in the matched check.
First-fit decreasing
First-fit decreasing changes one preliminary step: sort the list into decreasing order, then apply the ordinary first-fit rule. It does not mean choosing a different placement rule after sorting.
The sort can be done by inspection unless a particular sorting algorithm is explicitly requested. If quick sort is requested, its passes and pivots must be shown as well.
Worked example 3: sorting saves a bin
Question. Use first-fit decreasing to pack into bins of capacity .
Plan. Sort first, then scan existing bins from Bin 1 for each sorted item.
The first opens Bin 1 and the second opens Bin 2. The first fills Bin 1; the second fills Bin 2.
Why sort before packing? Placing the large items first reserves separate bins for them, leaving the smaller items to fill the gaps.
Answer. Bin 1: . Bin 2: .
Check. Without sorting, first-fit makes Bin 1: , Bin 2: , Bin 3: . The changed order saves a bin.
Worked example 4 changes only one item, from to . The final bin no longer fills exactly, but the algorithm is unchanged.
Worked example 4: an unfilled final space
Question. Use first-fit decreasing on , with capacity .
Plan. Sort the new list, then use the first available bin for every item.
The two items of size open Bins 1 and 2. The fills Bin 1, and the enters Bin 2.
Why not move the later to improve the appearance? First-fit decreasing is a prescribed procedure; do not rearrange its completed placements.
Answer. Bin 1: . Bin 2: .
Check. The total is , giving one unused unit across two bins of capacity .
The opening example has now been explained: first-fit decreasing uses two bins where first-fit in the original order uses three. However, it is still a heuristic, not a guarantee of optimality.
Watch out
Wrong: sort into increasing order before applying first-fit decreasing. Right: largest first. Also check earlier bins again when a small final item appears.
Add two small items in the next packing.
Bounds and proof of an optimal packing
A packing shows an upper bound on the minimum number of bins: it proves that many bins are sufficient. A lower bound proves that fewer bins cannot work.
Total-size lower bound
For total item size and bin capacity , any feasible packing needs at least
bins. Here is the least integer at least .
Not in the formula booklet: learn it.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account