Bin packing problem is to find the minimal number of bins of size v, which can contain all objects of size [s_1, s_2, s_3, ..., s_n]
I'm searching for a simple, non-trivial instance of the bin-packing problem.
A simple instance is an instance which can be solved with no more than 5 bins.
A non-trivial instance is an instance, which can't be solved by the best-fit-decreasing heuristic algorithm, but can be solved with complete search.
For example, the instance v = 20, objects = [15, 7, 14, 3, 14, 7, 9] is simple, but not non-trivial, because complete search proves that the minimal number of bins is 5:
[[15, 3], [7, 7], [14], [14], [9]]
however, best-fit heuristic also produces a 5-bin packing:
[[15], [14], [14], [9, 7, 3], [7]]
Does a simple, non-trivial instance of bin packing exist?
Indeed, such instance exists, namely:
v = 20, objects = [11, 7, 7, 6, 5, 3, 1]
Best-fit-decreasing heuristic gives:
[[11, 7], [7, 6, 5, 1], [3]]
Optimal packing is:
[[11, 6, 3], [7, 7, 5, 1]]