Но эти 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 миллион долларов — намного больше,
