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

Вы удивлялись, зачем мы вычисляем максимальную стоимость для рюкзаков меньшей емкости? Надеюсь, теперь все стало на свои места! Если в рюкзаке остается свободное место, вы можете использовать ответы на эти подзадачи для определения того, чем заполнить это пространство. Вместо магнитофона лучше взять ноутбук + гитару за $3500.

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

Итак, мы получили ответ: максимальная стоимость товаров, которые поместятся в рюкзак, равна $3500 — для гитары и ноутбука.

Возможно, вы подумали, что я воспользовался другой формулой для вычисления стоимости последней ячейки. Это связано с тем, что я опустил некоторые лишние сложности при заполнении предыдущих ячеек. Стоимость каждой ячейки вычисляется по постоянной формуле, которая выглядит так:

Применяя эту формулу к каждой ячейке таблицы, вы получите такую же таблицу, как у меня. Помните, что я говорил о решении подзадач? Вы объединили решения двух подзадач для решения еще одной, большей задачи.

Задача о рюкзаке: вопросы

Вам все еще кажется, что это какой-то фокус? В этом разделе я отвечу на некоторые часто задаваемые вопросы.

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

Представьте, что вы увидели четвертый предмет, который тоже можно засунуть в рюкзак! Вместе со всем предыдущим добром можно также украсть iPhone.

Придется ли пересчитывать все заново с новым предметом? Нет. Напомню, что динамическое программирование последовательно строит решение на основании вашей оценки. К настоящему моменту максимальные стоимости выглядят так:

Это означает, что в рюкзак с емкостью 4 фунта можно упаковать товары стоимостью до $3500. И вы полагали, что это итоговый максимум. Но давайте добавим новую строку для iPhone.

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

Начнем с первой ячейки. iPhone сам по себе помещается в рюкзак с емкостью 1 фунт. Старый максимум был равен $1500, но iPhone стоит $2000. Значит, берем iPhone.

В следующей ячейке можно разместить iPhone и гитару.

Для ячейки 3 ничего лучшего, чем снова взять iPhone вместе с гитарой, все равно не найдется, поэтому оставим этот вариант.

А вот в последней ячейке ситуация становится более интересной. Текущий максимум равен $3500. Вы снова можете взять iPhone, и у вас еще останется свободное место на 3 фунта.

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

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

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

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

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

Упражнения

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

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

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

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

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

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

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

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

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

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

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

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

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

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