Что-то никак не соображу как решать такую задачку (сформулирую ее в терминах задачи о рюкзаке):
Есть n предметов массой M1, M2, ... , Mn. И есть достаточное количество рюкзаков вместимостью V. Так вот нужно разложить предметы по рюкзакам чтобы минимизировать количество рюкзаков.
Помогите плиз если не сложно...
21.12.05 19:44: Перенесено модератором из 'Этюды для программистов' — Кодт
> Здравствуйте, Аноним, Вы писали:
Уважаемый модератор полагает, что в форуме 'Алгоритмы' читатели скорее найдут полиномиальный алгоритм для данной NP-hard задачи, чем в 'Этюдах' ?
Здравствуйте, NotImplemented, Вы писали:
NI>Уважаемый модератор полагает, что в форуме 'Алгоритмы' читатели скорее найдут полиномиальный алгоритм для данной NP-hard задачи, чем в 'Этюдах' ?
Ну зачем сразу полиномиальный... Хорошей эвристики было бы достаточно за глаза...
Здравствуйте, Черепнин Сергей, Вы писали:
ЧС> Масса и объём — это разные понятия. Я так понял вместо массы, даны объёмы предметов?
Ну или вместимость измеряется в килограммах
(например полиэтиленовые пакеты характеризуются не литрами которые в них влазят, а килограммами
) Как вам больше нравится.
ЧС> Первое что приходит в голову — это отсортировать предметы по объёму. И начинать вкладывать в рюкзаки начиная с больших...
То есть каждый рюкзак наполняем предметами по порядку убывания их массы? Такой жадный алгоритм даст приемлимую эвристику?
Если у предметов есть веса, но нет стоимости и задаче не в максимизации
стоимости выбранных предметов, а в минимизации использованных рюкзаков, то
это задача упаковки (bin packing). Есть набор эвристик, которые могут довать
приемлимые результаты: First Fit Decreasing, Best Fit
(Decreasing/Increasing), Wоrst Fit (D/I), Multifit?, и т.д.
Там еще есть тонкость: все предметы сразу даны или приходят один за одним?
Если они даны сразу (off-line), то их можно сортировать и это позволяет
получать лучшие результаты. Иначе надо принимать решение не зная что ждет в
будущем (on-line).
Эта задача неоднократно рассматривалась на этом форуме.
Posted via RSDN NNTP Server 2.0