7.03l, 7.03m - Packing algorithms

You already know

A greedy rule chooses what looks best at the current step. A heuristic can find a useful feasible answer without guaranteeing an optimum. The order in which a sorting or packing algorithm processes entries is part of its instructions.

Next-fit and first-fit

Next-fit: consider items in their given order. Put the next item in the current bin if it fits. Otherwise close that bin, open a new one and place it there. Never return to a closed bin.

First-fit: consider items in their given order. For each item, inspect existing bins in the order they were opened and place it in the first bin with enough space. Open a new bin only if none can hold it.

Worked example 1: the price of closing a bin

Question. Pack $6,6,4,4$, in that order, into bins of capacity $10$, using next-fit and first-fit. State each bin's contents.

Plan. Track the remaining space after each item; for first-fit, restart the search at bin $1$ every time.

Why this step? Next-fit cannot reopen bin $1$, even though its spare $4$ units would hold the next $4$. First-fit explicitly checks that bin first.

Answer. Next-fit uses $3$ bins: $(6)$, $(6,4)$, $(4)$. First-fit uses $2$: $(6,4)$, $(6,4)$.

Check. Every bin total is at most $10$, and the total item size is $20$, so fewer than $2$ bins is impossible. First-fit is optimal for this input.

Worked example 2: two different complements

Question. Use both methods on $7,6,4,3$, with capacity $10$.

Plan. Keep the given order and test each new item against the bins allowed by the chosen rule.

The $4$ does not fit after $7$, so first-fit puts it with $6$. The final $3$ fits exactly after $7$.

Why this step? First-fit means the first bin that fits, not the bin most recently used and not the bin that would leave the least spare space.

Answer. Next-fit uses $3$ bins; first-fit uses $2$.

Check. The total size is $20$, and both first-fit bins total $10$, proving that two bins achieve the lower bound.

Watch out

Wrong: put an item in a later bin because it fills that bin exactly. Right: first-fit tests bins in opening order and takes the first feasible one, even if a later bin would be a tighter fit.

First-fit decreasing and full-bin packing

First-fit decreasing: sort the items into decreasing order, then apply first-fit to that sorted list.

Full-bin packing: look across the remaining items for a combination that fills a bin exactly, if possible; otherwise choose a combination with the largest total not exceeding capacity. Remove those items and repeat. If several combinations tie, use the tie rule stated in the question, or show which valid choice you make.

Worked example 3: decreasing order can still miss the optimum

Question. Pack $6,5,3,2,2,2$ into capacity-$10$ bins using first-fit decreasing and full-bin packing, with the tie rule above. Determine the minimum possible bin count.

Plan. Follow each rule, then compare its bin count with the total-size lower bound.

The list is already decreasing. First-fit decreasing produces

The first $2$ cannot fit after $6+3$, so it goes with $5$; the second joins it, and the third opens a new bin.

For full-bin packing,

Why this step? A feasible two-bin packing and a lower bound of two together prove optimality; the rule's name alone does not.

Answer. First-fit decreasing uses $3$ bins; full-bin uses $2$. The minimum is $2$.

Check. The full-bin packing uses all six items exactly once, and each bin totals $10$.

Worked example 4: a changed capacity

Question. Apply the same methods to $6,5,3,2,2,2$ with capacity $12$, retaining the full-bin tie rule. Determine the minimum bin count.

Plan. Recompute every fit using the new capacity, then round the capacity bound upwards.

Why this step? Rounding $20/12$ down would suggest one bin, whose capacity is less than the total size.

Answer. Both methods use $2$ bins, which is optimal for this input.

Check. Both sets of totals sum to $20$, and none exceeds $12$.

Watch out

Wrong: the capacity lower bound is automatically achievable. Right: it is only a lower bound until you exhibit a packing that reaches it. Item sizes may prevent all the spare space from being combined usefully.

Online and offline packing

An online method processes each arriving item without knowing future items and makes its placement before the next arrives. An offline method has the complete item list available before making its packing decisions.

Key idea

Separate feasibility, the result produced by the named rule, and a proof of optimality. They are three different claims.