Answer the question
In order to leave comments, you need to log in
How to solve the container packing problem (one-dimensional)?
Good afternoon.
Faced with the task of distributing N elements of different dimensions in M containers of different dimensions. The complete condition is formulated as follows:
As input data, there are:
M - the number of containers, M numbers A1...An, corresponding to the capacity of the containers (in elements).
N - the number of elements, N numbers B1...Bn, respectively, the sizes of these elements.
The task is to give the optimal distribution of elements over containers in the following way:
Output N numbers, where the j-th number should indicate the number of the container in which we put the j-th element.
For example:
4 containers, with a capacity
of 11 7 4 3
5 elements, with a dimension
of 6 3 2 4 5
Conclusion (one of the possible):
1 2 4 2 1
Unfortunately, I am not strong in algorithms and NP-problems, and so far there are not very many ideas on this topic. I thought about sorting from largest to smallest and a simple search for filling - i.e. try to use the largest container as best as possible, then the second one behind it, etc., but in this case I have a problem of maintaining the original indexing (order).
Tell me, please, either articles to read on this topic, or a suitable algorithm. Thanks in advance)
Answer the question
In order to leave comments, you need to log in
Didn't find what you were looking for?
Ask your questionAsk a Question
731 491 924 answers to any question