Команде организаторов требуется последовательно провести n мероприятий в указанном порядке. Для каждого мероприятия задан (непустой) список городов, готовых принять это мероприятие. Всего рассматривается четыре крупных города, и для каждой пары городов задана стоимость переезда команды организаторов из одного города в другой. Предложите алгоритм с временем работы O(n), вычисляющий, в каких городах нужно проводить мероприятия, чтобы максимально сэкономить на переездах. Может ли существовать алгоритм, который работает быстрее?

задан 5 Апр '16 21:50

10|600 символов нужно символов осталось
1

Здесь работает метод динамического программирования.

Составляем 4 массива, по числу крупных городов. Для каждого $%1\le k\le n$% находим последовательно значения всех массивов. Изначально (при $%k=1$%) все значения равны нулю. Далее при $%k > 1$% полагаем $%A_j[k]$% равным минимуму значений четырёх величин: $%A_i[k-1]+p[i,j]$%, где $%1\le i\le4$%, и $%p[i,j]$% есть стоимость проезда из города $%i$% в город $%j$%. При этом число $%A_j[k]$% будет равно минимальной стоимости проведения $%k$% мероприятий, при условии, что они заканчиваются в $%j$%-м городе.

Ответ будет равен минимуму из четырёх чисел вида $%A_j[n]$%, где $%j=1,2,3,4$%.

ссылка

отвечен 6 Апр '16 3:11

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×544
×239
×42

задан
5 Апр '16 21:50

показан
525 раз

обновлен
6 Апр '16 3:11

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru