Грокаем алгоритмы

Допустим, вы можете выбирать из следующих товаров.

Фунт киноа стоит дороже, чем фунт любого другого товара. А раз так — набирайте столько киноа, сколько сможете унести! И если вам удастся набить им свой рюкзак, то это и будет лучшее из возможных решений.

Если киноа кончится, а в рюкзаке еще остается свободное место, возьмите следующий по ценности товар и т.д.

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

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

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

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

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

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

Взаимозависимые элементы

Предположим, вы хотите посетить Париж и добавили в свой список пару элементов.

На их посещение потребуется много времени, потому что сначала придется приехать из Лондона в Париж. Переезд отнимает полдня. Если вы захотите посмотреть все 3 достопримечательности, осмотр займет 4,5 дня.

Стоп, небольшая поправка. Вам не обязательно приезжать в Париж ради каждой достопримечательности. После того как вы там окажетесь, каждый последующий элемент займет всего один день. Следовательно, потребуется 1 день на каждую достопримечательность + 1 день на переезды = 3,5 дня, а не 4,5.

Если вы положите Эйфелеву башню в свой «рюкзак», то Лувр станет «дешевле» — он займет всего 1 день вместо 1,5 дня. Как смоделировать это обстоятельство в динамическом программировании?

Никак. Динамическое программирование — мощный метод, способный решать подзадачи и использовать полученные ответы для решения большой задачи. Динамическое программирование работает только в том случае, если каждая подзадача автономна, то есть не зависит от других подзадач. Из этого следует, что учесть поездки в Париж в алгоритме динамического программирования не удастся.

Может ли оказаться, что решение требует более двух «подрюкзаков»?

Может оказаться, что в лучшем решении должны отбираться больше двух элементов. В текущем варианте алгоритма объединяются не более двух «подрюкзаков» — больше двух их не бывает. Однако вполне возможно, что у этих «подрюкзаков» будут собственные «подрюкзаки».

Возможно ли, что при лучшем решении в рюкзаке остается пустое место?

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

Бриллиант очень крупный: он весит 3,5 фунта и стоит 1 миллион долларов — намного больше, чем любые другие предметы. Безусловно, нужно брать именно его! Но в рюкзаке остается еще пустое место на 0,5 фунта, и в нем ничего не поместится.

Упражнения

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

• вода, 3 фунта, 10;

• книга, 1 фунт, 3;

• еда, 2 фунта, 9;

• куртка, 2 фунта, 5;

• камера, 1 фунт, 6

Как выглядит оптимальный набор предметов для похода?

Самая длинная общая подстрока

Мы рассмотрели одну задачу динамического программирования. Какие выводы из нее можно сделать?

• Динамическое программирование применяется для оптимизации какой-либо характеристики при заданных ограничениях. В задаче о рюкзаке требуется максимизировать стоимость отобранных предметов с ограничениями по емкости рюкзака.

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

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

• в каждом решении из области динамического программирования строится таблица;

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

• каждая ячейка представляет подзадачу, поэтому вы должны подумать о том, как разбить задачу на подзадачи. Это поможет вам определиться с осями.