3.25

Key idea: keep the free capacities of the currently open bins in an ordered container that supports
1) search for the smallest / largest key that is ≥ a given number, and
2) insertion & deletion in O(log m) time (m ≤ n).

A balanced binary–search tree or C++ multiset<double> (Java TreeMultiset, Python bisect + list) suffices.

──────────────────────────────────────────────
Best-fit heuristic
bestFit(weights):
  S = empty ordered multiset  # stores free capacities
  bins = 0
  for w in weights:
    it = S.lower_bound(w) # smallest capacity ≥ w
    if it == S.end():
      bins += 1
      if w < 1: S.insert(1-w) # new bin’s remaining space
    else:
      c = *it; S.erase(it) # use that bin
      if c != w: S.insert(c-w) # still room left
  return bins
Each iteration performs ≤ 2 tree operations ⇒ total time [math]O(n\log n)[/math]; at most n capacities are stored.

──────────────────────────────────────────────
Worst-fit heuristic
Only the search line changes: we need the largest capacity that can hold the item.
worstFit(weights):
  S = empty ordered multiset
  bins = 0
  for w in weights:
    it = S.upper_bound(1) # past-the-end
    if it != S.begin():
      --it # now points to max capacity
      if *it >= w: # fits?
        c = *it; S.erase(it);
        if c != w: S.insert(c-w);
      else it = S.end(); # no suitable bin
    if it == S.end():
      bins += 1;
      if w < 1: S.insert(1-w);
  return bins
Again we perform ≤ 2 tree updates per object ⇒ [math]O(n\log n)[/math] time and [math]O(n)[/math] memory.

Thus both best-fit and worst-fit can be realised within the required [math]O(n\log n)[/math] bound.

Back to Chapter 3