Packing in a fixed number of boxes

Question

I am looking for an algorithm that will solve my problem in the most efficient way.

Description of the problem:

I have a list of elements (only positive integers are allowed) and a fixed number of boxes of the same capacity. So far I have been thinking about a branching algorithm, but I'm not quite sure if this is the best approach in this case.

Example:

Given a list of items:

(3, 4, 4, 2, 3, 9, 2) 

and three cells of capacity 9 each I need to pack them: (the order of the elements does not matter)

 [3, 4, 2], [4, 3, 2], [9] 

I think this is a variant of the packaging problem (I know NP-complete), but since I am not trying to minimize the number of drawers used, I wonder if there is a better solution.

Answer 1

This is a multibin packaging problem:

Given a set of elements, each of a certain size and a set of bins, each of a certain size - is there a distribution of objects in the bins so that no elements are unpacked and the bin capacity is not exceeded?

All in all, NP-hard. However, there are a few special cases that can be resolved efficiently, roughly, or even optimally.

see Discipline Wolfgang Steel Aus Göppingen

Answer 2

This is equivalent to the problem of packing the basket, given the number of boxes, maximizing the number of items packed in bins.

If the optimal solution is greater than or equal to the number of items in your list, the solution is also your solution to the problem. If the optimal solution is less than the number of items in your list, you do not have a solution to your problem.

Since the problem of packing NP-Hard baskets, your problem also does not have a polynomial time solution. You can use heuristics designed for the problem of packing a basket, for example, the best fit, first fit, and so on. But they do not guarantee that the optimal solution will be found.