Необходимо распределить конечное множество элементов (для каждго элемента известен размер) по фиксированному числу контейнеров (размер которых известен и одинаков для всех контейнеров). Перебор не годится.

Хотелось бы получить ссылку на материалы по теме ( в идеале алгоритм )

Прошу извинить, если это уже было.

Сортировка элементов по размерам и затем наполнение по нисходящей.

Цитата

Сортировка элементов по размерам и затем наполнение по нисходящей.

данный вариант не обязательно оптимальный

ИМХО данная задача является одним из вариантов задачи о рюкзаке...
а предложенный выше алгоритм очень похож "жадный"

@lex

Цитата

данная задача является одним из вариантов задачи о рюкзаке

однозначно - наполнение каждого отдельно взятого контейнера есть задача о рюкзаке

Цитата

данный вариант не обязательно оптимальный

не всегда сходящийся - верно. а вот среди прибизительных - имхо таки оптимальный.

Если заранее известно, что можно разместить ВСЕ предметы и нужно лишь найти правильное размещение, то жадный алгоритм оптимален.

Мне кажется, что тут жадный не даст оптимального размещения. Думаю, что тут надо использовать динамическое программирование.

Можно поэкспериментировать с генетикой, но требуется много времени.

Цитата(neutrino @ 31.7.2004, 20:41)

Можно поэкспериментировать с генетикой, но требуется много времени.

Блин, народ, уже вторую мессагу вижу с фразой "можно попробывать ГА, но он медленный" - да с чего вы это взяли? Нормально реализованный ГА на задачах подобных описанной дает весьма приемлемое время.. Единственная проблема - алгоритм никогда не останавливается сам и если делать ограничение по времени то никогда не знаешь - нашел ли он оптимальное решение. С другой стороны, на NP задачах (где и нужно применять ГА) вообще трудно говорить об оптимальном решении - на то они и NP ;)

И вообще по поводу скорости - подобные задачи обычно не требуют realtime решения, тобишь решаются они один раз (или давольно редко) т.ч. потратить время не жалко (тем более что речь идет не о годах, и даже не о днях ;)

А задачу о рюкзаке и о контейнерах моя реализация решела минут 10, и то это время я выдержал "на всякий случай" - конечное решение было не на много лучше решения найденнного за первую минуту... (кстати размер задачи в случае с ГА связан со временем/качеством далего не линейно, тобишь время/гачество изменяется гораздо медленнее размера, что есть гуд).

Если же ваш ГА решает эту задачу медленно или "не качественно" ;) то стоит обратить внимание на оценочную функцию и выбранные операторы ГА.

А не кажется ли вам, что эту задачу можно свести к задаче о рюкзаке...

Цитата(Yuri @ 2.8.2004, 09:30)

Блин, народ, уже вторую мессагу вижу с фразой "можно попробывать ГА, но он медленный" - да с чего вы это взяли?

А где это я сказал, что алгоритм медленный? Наоборот самый быстрый. Я имел в виду, что подбор шансов, кросовера, функции мутаций - долгая песня.

Кстати, есть ли проги для разработки эволюц. алг.?
Добавлено @ 15:31

Цитата

конечное решение было не на много лучше решения найденнного за первую минуту... (кстати размер задачи в случае с ГА связан со временем/качеством далего не линейно, тобишь время/гачество изменяется гораздо медленнее размера, что есть гуд).

Оно и верно - за первые несколько поколений эффективность растет очень быстро, а дальше очень медленно.

это 3DBPP (3-D Bin Packing Problem) ...
статью хорошую что-то сейчас не нашел, хотя где-то в инете она была... поищи по фразам 3dbpp, авторы martello, pisinger, vigo...
вот ссылка на код по этой статье...
http://www.diku.dk/hjemmesider/ansatte/pisinger/test3dbpp.c

омг некропост, аж 5лет прошло о_О

нууу, может быть и некро... но я сам сейчас над этой задачей бьюсь, а нормального готового алгоритма найти не могу...