|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
08.11.2009, 16:43 | #1 |
Пользователь
Регистрация: 02.11.2009
Сообщений: 24
|
Алгоритм решения "задачи радиста"
Подскажите пожалуйста алгоритм решения следующей задачи:
Радисту назначены два сеанса связи с продолжительностью Т1 и Т2 соответственно. За время этих сеансов требуется передать максимально возможное количество из N сообщений. Длительность передачи одного сообщения Mi(i=1,2,..,N). Определить, какие сообщения должны быть переданы в каждом из сеансов. Программу постараюсь написать сама, а вот алгоритм придумать не получается... Если у кого нибудь есть идеи - буду очень признательна. |
08.11.2009, 17:42 | #2 |
Максим Николаев
Форумчанин
Регистрация: 15.02.2009
Сообщений: 170
|
Я бы воспользовался простым перебором. Если нет каких либо специальных требований к алгоритму - то полный перебор - самое оно. При мощности современных компьютеров скорость работы будет вполне приемлемая, я бы даже сказал мгновенная.
Или можно свести данную задачу к задачи линейного программирования, и применять какой либо алгоритм линейного программирования, а чтобы не изобретать велосипед, можно использовать готовую программу для решения задач линейного программирования как модуль к своей, т.е. подкидывать ей данные, запускать её, брать результат её работы. Но это все излишне трудоемко, и если нет препятствий для использования простого перебора - то лучше использовать его.
NeshSoft. Программирование на заказ для студентов. Delphi/Pascal. Подробнее на сайте neshsoft.narod.ru
|
08.11.2009, 18:36 | #3 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Можно узнать ограничения? В зависимости от ограничений, 2 основных варианта алго, которые мне приходят в голову - бинарный "битовый" перебор и алгоритм "рюкзака".
|
08.11.2009, 18:43 | #4 |
Пользователь
Регистрация: 02.11.2009
Сообщений: 24
|
Никаких ограничений нет (я привела полный текст задания).
|
08.11.2009, 19:04 | #5 |
Максим Николаев
Форумчанин
Регистрация: 15.02.2009
Сообщений: 170
|
Его я и подразумевал под словами полный перебор. Оптимальный вариант помоему. А задача о рюкзаке - она, по сути, и сводится к такому перебору. Вообще все более менее простые и доступные алгоритмы не дают 100% оптимального решение, которое дает полный (бинарный) перебор.
NeshSoft. Программирование на заказ для студентов. Delphi/Pascal. Подробнее на сайте neshsoft.narod.ru
|
08.11.2009, 22:10 | #6 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
По поводу полного перебора - согласен, а вот по поводу рюкзака... Когда есть конечное сравнительно небольшое количество значений в множестве вариантов, то лучше использовать приемы ДП - ведь тогда сложность алгоритма ниже будет.
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
при вводе на листе "магазин"- код товара появлялось "описание" товара из "склада" с "продажной ценой" | aleksei78 | Microsoft Office Excel | 13 | 25.08.2009 12:04 |
Паскаль. 2 задачи (Программа "Верификация","КАК БРИГАДИРУ РАЗДЕЛИТЬ ЗАРОБОТАННЫЕ ДЕНЬГИ") | Valik102 | Помощь студентам | 3 | 20.05.2009 20:42 |
Оптимизация решения транспортной задачи методом "ступенек" | EvKont | Помощь студентам | 0 | 26.04.2009 14:51 |
"Транспортная задача", "Поиск решения" | Perroman | Microsoft Office Excel | 3 | 12.12.2007 17:12 |