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

Каждый алгоритм динамического программирования начинается с таблицы. Вот как выглядит таблица для задачи о рюкзаке.

Строки таблицы представляют предметы, а столбцы — емкость рюкзака от 1 до 4 фунтов. Все эти столбцы нужны, потому что они упрощают вычисление стоимостей «подрюкзаков».

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

Строка Гитара

Точная формула для вычисления значений в таблице будет приведена позднее, а пока ограничимся общим описанием. Начнем с первой строки.

Строка снабжена пометкой «гитара»; это означает, что вы пытаетесь уложить гитару в рюкзак. В каждой ячейке принимается простое решение: класть гитару в рюкзак или нет? Помните: мы пытаемся найти множество элементов с максимальной стоимостью.

В первой ячейке емкость рюкзака равна 1 фунту. Гитара также весит 1 фунт — значит, она поместится в рюкзак! Итак, стоимость этой ячейки составляет $1500, а в рюкзаке лежит гитара.

Начнем заполнять ячейку.

По тому же принципу каждая ячейка в таблице содержит список всех элементов, которые помещаются в рюкзаке на данный момент.

Посмотрим на следующую ячейку. На этот раз емкость рюкзака составляет 2 фунта. Понятно, что гитара здесь поместится!

Процедура повторяется для остальных ячеек строки. Вспомните, что текущей является первая строка, поэтому выбирать приходится только из одного предмета — гитары. Считайте, что два других предмета пока недоступны.

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

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

Помните, что мы стремимся обеспечить максимальную стоимость предметов в рюкзаке. Эта строка представляет текущую лучшую оценку максимума. Итак, на данный момент из этой строки следует, что для рюкзака с емкостью 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. Следовательно, настоящее сравнение выглядит так: