Packing items into fixed number of bins

Question

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.

Answer 1

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.

see Wolfgang Stille aus Göppingen's thesis

Answer 2

This is equivalent to the bin packing problem, given a number of bins, maximizing the number of items packed into the bins.

If the optimal solution is larger than or equal to the number of the items in your list, the solution is also your problem's solution. If the optimal solution is less than the number of the items in your list, there is no solution to your problem.

Since the bin packing problem is NP-Hard, there is no polynomial time solution to your problem either. You can use the heuristics developed for the bin packing problem, such as best fit, first fit and so on. But they do not guarantee the optimal solution to be found.