I am looking for an algorithm that will solve my problem in the most efficient way.
Problem description:
I have a list of items (only positive integers are allowed) and fixed number of bins of identical capacity. So far, I thought about branch-and-bound algorithm, but I am not quite sure if it is the best approach in this case.
Example:
Given a list of items:
(3, 4, 4, 2, 3, 9, 2)
and three bins of capacity 9 each I need to pack them this: (order of items is irrelevant)
[3, 4, 2], [4, 3, 2], [9]
I think this is a variant of the bin-packing problem (which I know is NP-complete), but since I am not trying to minimize number of bins used I wonder if there is a better solution.
This is the multibin packing problem:
Given a set of items, each of a specific size, and a set of bins, each of a specific size as well – is there a distribution of items to bins such that no item is left unpacked and no bin capacity is exceeded?
In general it is NP-hard. However, there are several special cases that may be solved efficiently, either approximately or even optimally.