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

[kitty19]

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

[NeshSoft]

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

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

[LeBron]

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

[kitty19]

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

[NeshSoft]

Сообщение от LeBron

бинарный "битовый" перебор

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

[LeBron]

Сообщение от NeshSoft

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

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