Non-trivial bin-packing instance with 5 objects. 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], [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$?
 A: No, there is no such instance for any $n\le 5$. Indeed, assume to the contrary. Pick the smallest $n$ for which $O<A$, where $O$ is the number of bins in an optimal packing and $A$ be the number of bins in a packing found by best-fit-decreasing heuristic. Enumerate the objects in such an order that $s_1\ge s_2\ge\dots\ge s_n$. Now we use the following simple observations.
If $O=1$ then $A=1$.
Assume that in an optimal packing there exists a bin containing only one object. But, since $s_1\le v$, without loss of generality we may assume that the bin contains Object 1 and the other objects placed into the first bin by best-fit-decreasing heuristic. Removing these objects from the object list, we reduce the problem to a smaller number of objects, which  contradicts the minimality of $n$. 
The above observations imply that $O=2$, because otherwise since $n<6$ in each optimal packing there exists a bin containing only one object. Now fix and optimal packing and consider a bin containing Object $1$. If the bin contains at lest two other objects then it can be easily checked that $A=2$. If the bin contains at most one other object $i$ then the other bin contains all remaining objects. Then in the packing created by best-fit-decreasing heuristic the first bin contains at least Object $1$ and Object $j$ with $j\le i$, so the second bin contains all other objects, because it is able to contain them, so $A=2$.
A: Define a set of objects $x_1,x_2, ... ,x_k$ to dominate a set of objects $y_1,y_2, ... ,y_l$ if $k\ge l$ and $x_i\ge y_i$ for $1\ge i\ge l.$ If set $X$ dominates set $Y$, then the existence of a solution with $n$ bins for $X$ implies a solution with $n$ bins for $Y$. 
Now suppose there to be a solution with fewer bins {$A_i$} than the first-fit solution and let $B_1$ be the first bin in the first-fit solution. The contents of $B_1$ cannot be dominated by the contents of any $A_i$ by definition of the first-fit algorithm. Furthermore, the contents of $B_1$ cannot  dominate  the contents of any $A_i$, for if it did then the objects remaining for the other $B_i$ would be dominated by those remaining for the other $A_i$ and we would have another  non-trivial bin packing with fewer objects and we can restrict this analysis to that smaller example!
Let $A_1$ be a bin containing the largest object $s$. Now  $B_1$ must, of course, contains $s$ and the non-dominating result means that $B_1$ must contain at least two objects. The non-dominating result then means that each $A_i$ must contain at least three objects and this is why $n$ must be at least 6.  
