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

Но эти 3 фунта можно заполнить на $2000! $2000 от iPhone + $2000 из старой подзадачи: получается $4000. Новый максимум!

Вот как выглядит новая завершающая таблица.

Вопрос: может ли значение в столбце уменьшиться? Такое возможно?

Подумайте над ответом, прежде чем продолжить чтение.

Ответ: нет. При каждой итерации сохраняется текущая оценка максимума. Эта оценка ни при каких условиях не может быть меньше предыдущей!

Упражнения

9.1 Предположим, к предметам добавился еще один: MP3-плеер. Он весит 1 фунт и стоит $1000. Стоит ли брать его?

Что произойдет при изменении порядка строк?

Изменится ли ответ? Допустим, строки заполняются в другом порядке: магнитофон, ноутбук, гитара. Как будет выглядеть таблица? Заполните таблицу самостоятельно, прежде чем двигаться дальше.

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

Ответ не изменился. Он не зависит от порядка строк.

Можно ли заполнять таблицу по столбцам, а не по строкам?

Попробуйте сами! В данной задаче это ни на что не влияет, но в других задачах возможны изменения.

Что произойдет при добавлении меньшего элемента?

Допустим, вы можете выбрать ожерелье, которое весит 0,5 фунта и стоит $1000. Пока структура таблицы предполагает, что все веса являются целыми числами. Теперь вы решаете взять ожерелье. Остается еще 3,5 фунта. Какую максимальную стоимость можно разместить в объеме 3,5 фунта? Неизвестно! Вы вычисляли стоимость только для рюкзаков с емкостью 1, 2, 3 и 4 фунта. Теперь придется определять стоимость для рюкзака на 3,5 фунта.

Из-за ожерелья приходится повысить точность представления весов, поэтому таблица должна измениться.

Можно ли взять часть предмета?

Допустим, вы наполняете рюкзак в продуктовом магазине. Вы можете украсть мешки с чечевицей и рисом. Если весь мешок не помещается, его можно открыть и отсыпать столько, сколько унесете. В этом случае вы уже не действуете по принципу «все или ничего» — можно взять только часть предмета. Как решить такую задачу методом динамического программирования?

Ответ: никак. В решении, полученном методом динамического программирования, вы либо берете предмет, либо не берете. Алгоритм не преду­сматривает возможность взять половину предмета.

Однако проблема легко решается с помощью жадного алгоритма! Сначала вы берете самый ценный предмет — настолько большую его часть, насколько возможно. Когда самый ценный предмет будет исчерпан, вы берете максимально возможную часть следующего по ценности предмета и т.д.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Бриллиант очень крупный: он весит 3,5 фунта и стоит 1 миллион долларов — намного больше,