M
M
Mikhail Neverov2014-01-09 10:47:03
C++ / C#
Mikhail Neverov, 2014-01-09 10:47:03

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

2 answer(s)
A
Andrew, 2014-01-09
@StivenLH

Try: www.rsdn.ru/forum/alg/4305230.all

G
GavriKos, 2014-01-09
@GavriKos

Can be solved with a genetic algorithm. An example that can certainly be found is the task of packing a backpack.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question