Page 224 - Bkhargava_-_Grokaem_algoritmy

Упражнения 223

Оптимизация туристического маршрута

Представьте, что вы приехали в Лондон на выходные. У вас два дня, а мест,
которые хочется посетить, слишком много. Побывать везде не получится,
поэтому вы составляете список.

D..ОС.ТОП РИМ Е. Ч АТЕ.ЛЬНОС.ТЬ ЬPE.MJI ОЦЕ.НКА
1
ЬЕ.С.ТМИНС.ТЕ.РС.КОЕ. АББАТСТ&О 1 .D.HJI :f
1
ТЕ.АТР •ГЛОБУС• 1 1 .D.HJI 6
1
1-\ЩMOHMbHAJI rME.PE.JI \ .D.E.H Ь CJ
БРИТАНС.КИll. MYJE.11. 2. .D.HJI ~

СОБОР С6. ЛА6ЛА 1 1 .D.HJI ~
1

Для каждой достопримечательности, которую вы захотите увидеть, вы ука­
зываете, сколько времени займет осмотр и насколько сильно вы хотите ее
увидеть. Сможете ли вы построить оптимальный туристический маршрут
на основании этого списка?

Да это все та же задача о рюкзаке! Вместо ограниченной емкости рюкзака -
ограниченное время. Вместо магнитофонов и ноутбуков - список мест,
которые вы хотите посетить. Нарисуйте таблицу динамического програм­
мирования для списка, прежде чем двигаться дальше.

Вот как должна выглядеть эта таблица:

l.z 1 ~2 2

ЬЕ.СТМИНСТЕ.Р
ТЕАТР •ГЛОБУС•
НЩИОНМЬНАJI ПЛЕ.РЕ.JI
l-----'~~1--~г---i
БРИПНСКИ!i. MYJE.li.
1--~-1--~1--~+---t
СОБОР С&. nА&ЛА

www.trk.kg