Допустим, вы можете выбирать из следующих товаров.
Фунт киноа стоит дороже, чем фунт любого другого товара. А раз так — набирайте столько киноа, сколько сможете унести! И если вам удастся набить им свой рюкзак, то это и будет лучшее из возможных решений.
Если киноа кончится, а в рюкзаке еще остается свободное место, возьмите следующий по ценности товар и т.д.
Оптимизация туристического маршрута
Представьте, что вы приехали в Лондон на выходные. У вас два дня, а мест, которые хочется посетить, слишком много. Побывать везде не получится, поэтому вы составляете список.
Для каждой достопримечательности, которую вы захотите увидеть, вы указываете, сколько времени займет осмотр и насколько сильно вы хотите ее увидеть. Сможете ли вы построить оптимальный туристический маршрут на основании этого списка?
Да это все та же задача о рюкзаке! Вместо ограниченной емкости рюкзака — ограниченное время. Вместо магнитофонов и ноутбуков — список мест, которые вы хотите посетить. Нарисуйте таблицу динамического программирования для списка, прежде чем двигаться дальше.
Вот как должна выглядеть эта таблица:
Вы изобразили ее правильно? Теперь заполните. Какие достопримечательности вы выберете? Ответ:
Взаимозависимые элементы
Предположим, вы хотите посетить Париж и добавили в свой список пару элементов.
На их посещение потребуется много времени, потому что сначала придется приехать из Лондона в Париж. Переезд отнимает полдня. Если вы захотите посмотреть все 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
Как выглядит оптимальный набор предметов для похода?
Мы рассмотрели одну задачу динамического программирования. Какие выводы из нее можно сделать?
• Динамическое программирование применяется для оптимизации какой-либо характеристики при заданных ограничениях. В задаче о рюкзаке требуется максимизировать стоимость отобранных предметов с ограничениями по емкости рюкзака.
• Динамическое программирование работает только в ситуациях, в которых задача может быть разбита на автономные подзадачи, не зависящие друг от друга.
Построить решение на базе динамического программирования бывает непросто. В этом разделе мы сосредоточимся на этой теме. Несколько общих рекомендаций:
• в каждом решении из области динамического программирования строится таблица;
• значения ячеек таблицы обычно соответствуют оптимизируемой характеристике. Для задачи о рюкзаке значения представляли общую стоимость товаров;
• каждая ячейка представляет подзадачу, поэтому вы должны подумать о том, как разбить задачу на подзадачи. Это поможет вам определиться с осями.
