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

После того как первая строка будет заполнена, таблица будет выглядеть так:

Помните, что мы стремимся обеспечить максимальную стоимость предметов в рюкзаке. Эта строка представляет текущую лучшую оценку максимума. Итак, на данный момент из этой строки следует, что для рюкзака с емкостью 4 фунта максимальная стоимость предметов составит $1500.

Вы знаете, что это решение неокончательно. В процессе работы алгоритма оценка будет уточняться.

Магнитофон

Займемся следующей строкой, которая относится к магнитофону. Теперь, когда вы перешли ко второй строке, появляется выбор между магнитофоном и гитарой. В каждой строке можно взять предмет этой строки или предметы, находящиеся в верхних строках. Таким образом, сейчас нельзя выбрать ноутбук, но можно выбрать магнитофон и/или гитару. Начнем с первой ячейки (рюкзак с емкостью 1 фунт). Текущая максимальная стоимость предметов, которые можно положить в рюкзак с емкостью 1 фунт, составляет $1500.

Брать магнитофон или нет?

Емкость рюкзака составляет 1 фунт. Поместится туда магнитофон? Нет, он слишком тяжел! Так как магнитофон не помещается в рюкзак, максимальная оценка для 1-фунтового рюкзака остается равной $1500.

То же самое происходит со следующими двумя клетками. Емкость этих рюкзаков составляет 2 и 3 фунта соответственно. Старая максимальная стоимость для обеих ячеек была равна $1500.

Магнитофон все равно не помещается, так что оценка остается неизменной.

А если емкость рюкзака увеличивается до 4 фунтов? Ага, магнитофон наконец-то войдет в рюкзак! Старая максимальная стоимость была равна $1500, но если вместо гитары положить магнитофон, она увеличится до $3000! Берем магнитофон.

Оценка только что обновилась! Имея рюкзак емкостью 4 фунта, вы можете положить в него товары стоимостью по крайней мере $3000. Из таблицы видно, что оценка постепенно возрастает.

Ноутбук

А теперь проделаем то же для ноутбука! Ноутбук весит 3 фунта, поэтому он не поместится в рюкзак с емкостью 1 или 2 фунта. Оценка для первых двух ячеек остается на уровне $1500.

Для 3 фунтов старая оценка составляла $1500. Но теперь вы можете выбрать ноутбук, который стоит $2000. Следовательно, новая максимальная оценка равна $2000!

При 4 фунтах ситуация становится по-настоящему интересной. Это очень важная часть. В настоящее время оценка составляет $3000. В рюкзак можно положить ноутбук, но он стоит всего $2000.

Так-так, старая оценка была лучше. Но постойте! Ноутбук весит всего 3 фунта, так что 1 фунт еще свободен! На это место можно еще что-нибудь положить.

Какую максимальную стоимость можно разместить в 1 фунте? Да вы же уже вычислили ее!

В соответствии с последней оценкой в свободном месте емкостью в 1 фунт можно разместить гитару стоимостью $1500. Следовательно, настоящее сравнение выглядит так:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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