Задача о рюкзаках, что ли? :)
От: Аноним  
Дата: 21.12.05 14:59
Оценка:
Что-то никак не соображу как решать такую задачку (сформулирую ее в терминах задачи о рюкзаке):

Есть n предметов массой M1, M2, ... , Mn. И есть достаточное количество рюкзаков вместимостью V. Так вот нужно разложить предметы по рюкзакам чтобы минимизировать количество рюкзаков.

Помогите плиз если не сложно...

21.12.05 19:44: Перенесено модератором из 'Этюды для программистов' — Кодт
Re: Задача о рюкзаках, что ли? :)
От: NotImplemented США github.com/NotImplemented
Дата: 21.12.05 17:24
Оценка:
> Здравствуйте, Аноним, Вы писали:

Уважаемый модератор полагает, что в форуме 'Алгоритмы' читатели скорее найдут полиномиальный алгоритм для данной NP-hard задачи, чем в 'Этюдах' ?
Re[2]: Задача о рюкзаках, что ли? :)
От: Аноним  
Дата: 21.12.05 23:19
Оценка:
Здравствуйте, NotImplemented, Вы писали:

NI>Уважаемый модератор полагает, что в форуме 'Алгоритмы' читатели скорее найдут полиномиальный алгоритм для данной NP-hard задачи, чем в 'Этюдах' ?


Ну зачем сразу полиномиальный... Хорошей эвристики было бы достаточно за глаза...
Re: Задача о рюкзаках, что ли? :)
От: Черепнин Сергей Украина  
Дата: 22.12.05 06:38
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Что-то никак не соображу как решать такую задачку (сформулирую ее в терминах задачи о рюкзаке):


А>Есть n предметов массой M1, M2, ... , Mn. И есть достаточное количество рюкзаков вместимостью V. Так вот нужно разложить предметы по рюкзакам чтобы минимизировать количество рюкзаков.


А>Помогите плиз если не сложно...


Масса и объём — это разные понятия. Я так понял вместо массы, даны объёмы предметов? Первое что приходит в голову — это отсортировать предметы по объёму. И начинать вкладывать в рюкзаки начиная с больших...
Re[2]: Задача о рюкзаках, что ли? :)
От: Аноним  
Дата: 22.12.05 08:20
Оценка:
Здравствуйте, Черепнин Сергей, Вы писали:

ЧС> Масса и объём — это разные понятия. Я так понял вместо массы, даны объёмы предметов?


Ну или вместимость измеряется в килограммах (например полиэтиленовые пакеты характеризуются не литрами которые в них влазят, а килограммами ) Как вам больше нравится.

ЧС> Первое что приходит в голову — это отсортировать предметы по объёму. И начинать вкладывать в рюкзаки начиная с больших...


То есть каждый рюкзак наполняем предметами по порядку убывания их массы? Такой жадный алгоритм даст приемлимую эвристику?
Re: Задача о рюкзаках, что ли? :)
От: Cruelty  
Дата: 22.12.05 10:44
Оценка:
Если у предметов есть веса, но нет стоимости и задаче не в максимизации
стоимости выбранных предметов, а в минимизации использованных рюкзаков, то
это задача упаковки (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
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.