Bin packing problem is a problem, where one has to find the minimum number of bins of size $v$ required to store $n$ objects of sizes $s_1, \ldots, s_n$. Object sizes are never greater than $v$.
For example, if $v = 10$ and the objects sizes are $2, 5, 4, 7, 1, 3, 8$, we can store objects with 3 bins: $[8, 2], [7, 3], [5, 4, 1]$, but not with 2 bins or less, as this would leave some items unpacked. Therefore 3 is the minimum number of bins required, and $[8, 2], [7, 3], [5, 4, 1]$ is an optimal solution.
The best-fit-decreasing heuristic is a packing strategy, which aims to produce a packing close to optimal. It first sorts all the items in descending order. Then it iterates over all items, and for each item attempts to find an existing bin, which can both fit the item and whose spare capacity is closest to the size of the item. If such bin exists, it puts the object in the bin. If it doesn't, it creates a new bin and puts it there.
A non-trivial bin-packing instance is an instance of the problem, which can't be optimally solved by the best-fit-decreasing heuristic.
For example, the instance $v = 7$, $n=6$ where sizes are $3, 2, 3, 2, 2, 2$ is non-trivial, because the best-fit decreasing heuristic will:
- Sort the items to give $3, 3, 2, 2, 2, 2$
- Put the first two items in the first bin, producing a bin $[3, 3]$
- Put the next three items in the second bin, producing a bin $[2, 2, 2]$
- Put the last item in the third bin, producing a packing $[3, 3], [2, 2, 2], $
This is a valid packing, but non-optimal, as it requires 3 bins, and there exists a valid packing with two bins: $[3, 2, 2], [3, 2, 2]$.
Is there a non-trivial bin-packing instance with $n=5$?