Грокаем а Иллюстрированное пособие для программистов и любопытствующих

46/ФУНТ


ДАЛ
43/ФУНТ


РИС
4г/4>унт


опустим, вы можете выбирать из следующих товаров.
Фунт киноа стоит дороже, чем фунт любого другого товара. А раз так — на­бирайте столько киноа, сколько сможете унести! И если вам удастся набить им свой рюкзак, то это и будет лучшее из возможных решений.
РЮКЗАК
Н АБИТ
КИНОА
Если киноа кончится, а в рюкзаке еще остается свободное место, возьмите следующий по ценности товар и т. д.
Оптимизация туристического маршрута
Представьте, что вы приехали в Лондон на выходные. У вас два дня, а мест, которые хочется посетить, слишком много. Побывать везде не получится, поэтому вы составляете список.

ДОСТОПРИМЕЧАТЕЛЬНОСТЬ	БРЕМЯ	ОЦЕНКА
ЬЕСТМИНСТЕРСКОЕ АББАТСТ60	V, лня
ТЕАТР «ГЛОБУС*	V, лня	6
НАЦИОНАЛЬНАЯ ГАЛЕРЕЯ	1 ЛЕНЬ	Я
БРИТАНСКИЙ МУЗЕЙ	г лня	я
СОБОР ее. ПАВЛА	V, лня	г

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

Да это все та же задача о рюкзаке! Вместо ограниченной емкости рюкзака — ограниченное время. Вместо магнитофонов и ноутбуков — список мест, которые вы хотите посетить. Нарисуйте таблицу динамического програм­мирования для списка, прежде чем двигаться дальше.
В
ЬЕСТМИНСТЕР ТЕАТР «ГЛОБУС» НАЦИОНАЛЬНАЯ ГАЛЕРЕЯ БРИТАНСКИЙ МУЗЕЙ СОБОР С6. ПАВЛА


от как должна выглядеть эта таблица:
Вы изобразили ее правильно? Теперь заполните. Какие достопримечатель­ности вы выберете? Ответ:
В

К	1	IK	2
ь
X		-13- • <06	' ‘COO
ф 1	>1— Yb	'16­ *	■22.:
Х'	\Ъ Oi(rx
%	•is is	^s2\ ux>S	^4Z4

ОТВЕТ:
ВЕСТМИНСТЕРСКОЕ АББАТСТВО, НАЦИОНАЛЬНАЯ ГАЛЕРЕЯ, СОБОР СВ. ПАВЛА



ЕСТМИНСТЕР ТЕАТР «ГЛОБУС»
НАЦИОНАЛЬНАЯ ГАЛЕРЕЯ БРИТАНСКИЙ МУЗЕЙ СОБОР СВ. ПАВЛА
Взаимозависимые элементы
Предположим, вы хотите посетить Париж и добавили в свой список пару элементов.
Э

/i^Y 1	ъ
'/2okV 1	я
'/zW 1	л-

ЙФЕЛЕВА БАШНЯ ЛУВР
НОТР-ДАМ
На их посещение потребуется много времени, потому что сначала придется приехать из Лондона в Париж. Переезд отнимает полдня. Если вы захотите посмотреть все 3 достопримечательности, осмотр займет 4,5 дня.
Стоп, небольшая поправка. Вам не обязательно приезжать в Париж ради каждой достопримечательности. После того как вы там окажетесь, каждый
последующий элемент займет всего один день. Следовательно, потребуется 1 день на каждую достопримечательность + 1 день на переезды = 3,5 дня, а не 4,5.
Если вы положите Эйфелеву башню в свой «рюкзак», то Лувр станет «де­шевле» — он займет всего 1 день вместо 1,5 дня. Как смоделировать это обстоятельство в динамическом программировании?
Никак. Динамическое программирование — мощный метод, способный ре­шать подзадачи и использовать полученные ответы для решения большой задачи. Динамическое программирование работает только в том случае, если каждая подзадача автономна, то есть не зависит от других подзадач. Из этого следует, что учесть поездки в Париж в алгоритме динамического программирования не удастся.
Может ли оказаться, что решение требует более двух «подрюкзаков»?
М
НО МОГУТ БЫТЬ «ПОЛ- РЮКЗАКИ», КОТОРЫЕ СОДЕРЖАТ С0БСТ6 ЕН- НЫЕ «ПОДРЮКЗАКИ»


ТРЕК «П0ЛРЮКЗАК06» БЫТЬ НЕ МОЖЕТ


ожет оказаться, что в лучшем решении должны отбираться больше двух элементов. В текущем варианте алгоритма объединяются не более двух «подрюкзаков» — больше двух их не бывает. Однако вполне возможно, что у этих «подрюкзаков» будут собственные «подрюкзаки».
Возможно ли, что при лучшем решении в рюкзаке остается пустое место?
Д
//VW
а. Представьте, что вы можете также положить в рюкзак бриллиант.
Б
БРИЛЛИАНТ.
СТОИМОСТЬ 41 000 ООО,
ВЕС 3,5 ФУНТА
риллиант очень крупный: он весит 3,5 фунта и стоит 1 миллион долларов — намного больше, чем любые другие предметы. Безусловно, нужно брать именно его! Но в рюкзаке остается еще пустое место на 0,5 фунта, и в нем ничего не поместится.
Упражнения

2. 
   Предположим, что вы собираетесь в турпоход. Емкость вашего рюк­зака составляет б фунтов, и вы можете взять предметы из следующего списка. У каждого предмета имеется стоимость; чем она выше, тем важнее предмет:
   

• 
  вода, 3 фунта, 10;
  
• 
  книга, 1 фунт, 3;
  
• 
  еда, 2 фунта, 9;
  
• 
  куртка, 2 фунта, 5;
  
• 
  камера, 1 фунт, 6
  

Как выглядит оптимальный набор предметов для похода?
С
амая длинная общая подстрока
Мы рассмотрели одну задачу динамического про­граммирования. Какие выводы из нее можно сде­лать?
□ Динамическое программирование применяется для оптимизации какой-либо характеристики
при заданных ограничениях. В задаче о рюкзаке требуется максимизи­ровать стоимость отобранных предметов с ограничениями по емкости рюкзака.

• 
  Динамическое программирование работает только в ситуациях, в кото­рых задача может быть разбита на автономные подзадачи, не зависящие друг от друга.
  

Построить решение на базе динамического программирования бывает не­просто. В этом разделе мы сосредоточимся на этой теме. Несколько общих рекомендаций:

• 
  в каждом решении из области динамического программирования стро­ится таблица;
  
• 
  значения ячеек таблицы обычно соответствуют оптимизируемой ха­рактеристике. Для задачи о рюкзаке значения представляли общую стоимость товаров;
  
• 
  каждая ячейка представляет подзадачу, поэтому вы должны подумать о том, как разбить задачу на подзадачи. Э го поможет вам определиться с осями.
  

Р
ассмотрим еще один пример. Допустим, вы от­крыли сайт dictionary.com. Пользователь вводит слово, а сайт возвращает определение. Но если пользователь ввел несуществующее слово, нуж­но предположить, какое слово имелось в виду.
Алекс ищет определение «fish», но он случайно ввел «hish». Такого слова в словаре нет, но зато у вас есть список похожих слов.