Таблица должна выглядеть так:
Ответ не изменился. Он не зависит от порядка строк.
Можно ли заполнять таблицу по столбцам, а не по строкам?
Попробуйте сами! В данной задаче это ни на что не влияет, но в других задачах возможны изменения.
Что произойдет при добавлении меньшего элемента?
Допустим, вы можете выбрать ожерелье, которое весит 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 миллион долларов — намного больше, чем любые другие предметы. Безусловно, нужно брать именно его! Но в рюкзаке остается еще пустое место на 0,5 фунта, и в нем ничего не поместится.
Упражнения
9.2 Предположим, что вы собираетесь в турпоход. Емкость вашего рюкзака составляет 6 фунтов, и вы можете взять предметы из следующего списка. У каждого предмета имеется стоимость; чем она выше, тем важнее предмет:
• вода, 3 фунта, 10;
• книга, 1 фунт, 3;
• еда, 2 фунта, 9;
• куртка, 2 фунта, 5;
• камера, 1 фунт, 6
Как выглядит оптимальный набор предметов для похода?
Самая длинная общая подстрока
Мы рассмотрели одну задачу динамического программирования. Какие выводы из нее можно сделать?
• Динамическое программирование применяется для оптимизации какой-либо характеристики при заданных ограничениях. В задаче о рюкзаке требуется максимизировать стоимость отобранных предметов с ограничениями по емкости рюкзака.
• Динамическое программирование работает только в ситуациях, в которых задача может быть разбита на автономные подзадачи, не зависящие друг от друга.
Построить решение на базе динамического программирования бывает непросто. В этом разделе мы сосредоточимся на этой теме. Несколько общих рекомендаций:
• в каждом решении из области динамического программирования строится таблица;
• значения ячеек таблицы обычно соответствуют оптимизируемой характеристике. Для задачи о рюкзаке значения представляли общую стоимость товаров;
• каждая ячейка представляет подзадачу, поэтому вы должны подумать о том, как разбить задачу на подзадачи. Это поможет вам определиться с осями.
Рассмотрим еще один пример. Допустим, вы открыли сайт dictionary.com. Пользователь вводит слово, а сайт возвращает определение. Но если пользователь ввел несуществующее слово, нужно предположить, какое слово имелось в виду. Алекс ищет определение «fish», но он случайно ввел «hish». Такого слова в словаре нет, но зато у вас есть список похожих слов.
(Это несерьезный пример, поэтому список ограничен всего двумя словами. Вероятно, на практике такой список будет состоять из тысяч слов.)
Итак, Алекс ввел строку hish. Какое слово он хотел ввести на самом деле: fish или vista?
Построение таблицы
Как должна выглядеть таблица для этой задачи? Вы должны ответить на следующие вопросы.
• Какие значения должны содержаться в ячейках?
• Как разбить эту задачу на подзадачи?
• Каков смысл осей таблицы?
В динамическом программировании вы пытаетесь максимизировать некоторую характеристику. В данном случае ищется самая длинная подстрока, общая в двух словах. Какую общую подстроку содержат hish и fish? А как насчет hish и vista? Именно это требуется вычислить.
Как говорилось ранее, значения в ячейках обычно представляют ту характеристику, которую вы пытаетесь оптимизировать. Вероятно, в данном случае этой характеристикой будет число: длина самой длинной подстроки, общей для двух строк.
Как разделить эту задачу на подзадачи? Например, можно заняться сравнением подстрок. Вместо того чтобы сравнивать hish и fish, можно сначала сравнить his и fis. Каждая ячейка будет содержать длину самой длинной подстроки, общей для двух подстрок. Такое решение также подсказывает, что строками и столбцами таблицы, вероятно, будут два слова. А значит, таблица будет выглядеть примерно так:
Если у вас голова идет кругом, не огорчайтесь. Это сложный материал — собственно, именно поэтому я объясняю его в конце книги! Ниже будет приведено упражнение, чтобы вы могли самостоятельно потренироваться в динамическом программировании.
Заполнение таблицы
Сейчас вы уже достаточно хорошо представляете, как должна выглядеть таблица. По какой формуле заполняются ячейки таблицы? Мы можем немного упростить свою задачу, потому что уже знаем решение — у hish и fish имеется общая подстрока длины 3: ish.
Однако этот факт ничего не говорит о том, какая формула должна использоваться. Программисты иногда шутят об использовании алгоритма Фейнмана. Алгоритм Фейнмана, названный по имени известного физика Ричарда Фейнмана, работает так:
1. Записать формулировку задачи.
2. Хорошенько подумать.
3. Записать решение.
Да, программисты — большие шутники!
По правде говоря, простого способа вычислить формулу для данного случая не существует. Вам придется экспериментировать и искать работоспособное решение. Иногда алгоритм предоставляет не точный рецепт, а основу, на которую вы наращиваете свою идею.
Попробуйте предложить решение этой задачи самостоятельно. Даю подсказку — часть таблицы выглядит так:
Чему равны другие значения? Вспомните, что каждая ячейка содержит значение подзадачи. Почему ячейка (3, 3) содержит значение 2? Почему ячейка (3, 4) содержит значение 0?
Попытайтесь вывести формулу самостоятельно, прежде чем продолжить читать. Даже если вам не удастся получить правильный ответ, мои объяснения покажутся вам намного более понятными.