Алгоритм решения "задачи радиста"

Подскажите пожалуйста алгоритм решения следующей задачи: Радисту назначены два сеанса связи с продолжительностью Т1 и Т2 соответственно. За время этих сеансов требуется передать максимально возможное количество из N сообщений. Длительность передачи одного сообщения Mi(i=1,2,..,N). Определить, какие сообщения должны быть переданы в каждом из сеансов. Программу постараюсь написать сама, а вот алгоритм придумать не получается... Если у кого нибудь есть идеи - буду очень признательна.
5 ответов

Я бы воспользовался простым перебором. Если нет каких либо специальных требований к алгоритму - то полный перебор - самое оно. При мощности современных компьютеров скорость работы будет вполне приемлемая, я бы даже сказал мгновенная. Или можно свести данную задачу к задачи линейного программирования, и применять какой либо алгоритм линейного программирования, а чтобы не изобретать велосипед, можно использовать готовую программу для решения задач линейного программирования как модуль к своей, т.е. подкидывать ей данные, запускать её, брать результат её работы. Но это все излишне трудоемко, и если нет препятствий для использования простого перебора - то лучше использовать его.


Можно узнать ограничения? В зависимости от ограничений, 2 основных варианта алго, которые мне приходят в голову - бинарный "битовый" перебор и алгоритм "рюкзака".


Никаких ограничений нет (я привела полный текст задания).


бинарный "битовый" перебор
Его я и подразумевал под словами полный перебор. Оптимальный вариант помоему. А задача о рюкзаке - она, по сути, и сводится к такому перебору. Вообще все более менее простые и доступные алгоритмы не дают 100% оптимального решение, которое дает полный (бинарный) перебор.


Его я и подразумевал под словами полный перебор. Оптимальный вариант помоему. А задача о рюкзаке - она, по сути, и сводится к такому перебору.
По поводу полного перебора - согласен, а вот по поводу рюкзака... Когда есть конечное сравнительно небольшое количество значений в множестве вариантов, то лучше использовать приемы ДП - ведь тогда сложность алгоритма ниже будет.