Как решить задачу об упаковке в контейнеры (одномерная)?
Добрый день.
Столкнулся с задачей распределения N элементов различной размерности в M контейнеров различной размерности. Полностью условие формулируется вот так:
В качестве входных данных имеются:
M - число контейнеров, M чисел A1...An, соответствующий вместимости контейнеров(в элементах).
N - число элементов, N чисел B1...Bn, соответственно размеры этих элементов.
Задача состоит в том, чтобы выдать оптимальное распределение элементов по контейнерам в таком варианте:
Вывести N чисел, где j-тое число должно обозначать номер контейнера, в который мы кладем j-тый элемент.
К сожалению в алгоритмике и NP-задачах не силен, и пока своих идей на эту тему не очень много. Думал о сортировке от большего к меньшему и простому перебору на заполнение - т.е. попытаться как можно оптимальнее использовать самый большой контейнер, потом второй за ним и т.д., но в этом случае у меня встает проблема сохранения изначальной индексации(порядка).
Подскажите, пожалуйста, либо статьи на почитать на эту тему, либо подходящий алгоритм. Заранее спасибо)
@Flaker собственно говоря, я почерпнул идеи из приведенной OLS'ом статьи и начал экспериментировать с линейным раскроем. Он в данном случае является идеальным примером одномерной упаковки в контейнеры.
Задача об укладке рюкзака подразумевает один контейнер и несколько элементов. В нашем случае имеется M контейнеров, так что алгоритм с укладкой рюкзака, к сожалению, не подходит. Как его реализовать я как-раз знаю
Над генетическим алгоритмом пока сижу, разбираюсь, но кажется, что способ простого перебора проще, проблема скорее в том, как сохранять индексы начальных последовательностей.
