Вы знаете, что это решение неокончательно. В процессе работы алгоритма оценка будет уточняться.
Магнитофон
Займемся следующей строкой, которая относится к магнитофону. Теперь, когда вы перешли ко второй строке, появляется выбор между магнитофоном и гитарой. В каждой строке можно взять предмет этой строки или предметы, находящиеся в верхних строках. Таким образом, сейчас нельзя выбрать ноутбук, но можно выбрать магнитофон и/или гитару. Начнем с первой ячейки (рюкзак с емкостью 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.
Придется ли пересчитывать все заново с новым предметом? Нет. Напомню, что динамическое программирование последовательно строит решение на основании вашей оценки. К настоящему моменту максимальные стоимости выглядят так:
