9.1. Bin Packing

In the bin packing problem, we are given a collection of \(n\) items of sizes \(s_1, \ldots, s_n\). Each size \(s_i\) satisfies \(0 < s_i \le 1\). Our goal is to pack these items into as few bins of size \(1\) as possible. In other words, we want to partition the set \(S = \{s_1, \ldots, s_n\}\) into as few subsets \(B_1, \ldots, B_k\) as possible so that \(\sum_{s \in B_j} s \le 1\) for all \(1 \le j \le k\). From here on, we will not distinguish between an item and its size.

As example, we could have five items of size \(0.6\), \(0.3\), \(0.4\), \(0.7\), and \(1\). They require \(3\) bins to be packed if we pack the first and third item into a bin, the second and fourth item into a bin, and the fifth item into a bin. This fills every bin fully but does not overpack any bin because \(0.6 + 0.4 = 1\) and \(0.3 + 0.7 = 1\).

Figure 9.1: Coming soon!