• Вы освоите динамическое программирование — метод решения сложных задач, разбиваемых на подзадачи, которые решаются в первую очередь.
• Рассматриваются примеры, которые научат вас искать решения новых задач, основанные на методе динамического программирования.
Задача о рюкзаке
Вернемся к задаче о рюкзаке из главы 8. У вас есть рюкзак, в котором можно унести товары общим весом до 4 фунтов.
Есть три предмета, которые можно уложить в рюкзак.
Какие предметы следует положить в рюкзак, чтобы стоимость добычи была максимальной?
Простое решение
Простой алгоритм выглядит так: вы перебираете все возможные множества товаров и находите множество с максимальной стоимостью.
Такое решение работает, но очень медленно. Для 3 предметов приходится обработать 8 возможных множеств, для 4 — 16 и т.д. С каждым добавляемым предметом количество множеств удваивается! Этот алгоритм выполняется за время O(2^n), что очень, очень медленно.
Для любого сколько-нибудь значительного количества предметов это неприемлемо. В главе 8 вы видели, как вычисляются приближенные решения. Такие решения близки к оптимальным, но могут не совпадать с ними.
Как же вычислить оптимальное решение?
Динамическое программирование
Ответ: с помощью динамического программирования! Давайте посмотрим, как работает этот метод. Процедура начинается с решения подзадач с постепенным переходом к решению полной задачи.
В задаче о рюкзаке начать следует с решения задачи для меньшего рюкзака (или «подрюкзака»), а потом на этой основе попытаться решить исходную задачу.
Динамическое программирование — достаточно сложная концепция; не огорчайтесь, если после первого прочтения что-то останется непонятным. Примеры помогут вам разобраться в теме.
Для начала я покажу вам алгоритм в действии. После этого у вас наверняка появится много вопросов! Я постараюсь ответить на них.
Каждый алгоритм динамического программирования начинается с таблицы. Вот как выглядит таблица для задачи о рюкзаке.
Строки таблицы представляют предметы, а столбцы — емкость рюкзака от 1 до 4 фунтов. Все эти столбцы нужны, потому что они упрощают вычисление стоимостей «подрюкзаков».
В исходном состоянии таблица пуста. Нам предстоит заполнить каждую ячейку таблицы. После того как таблица будет заполнена, вы получите ответ на свою задачу. Пожалуйста, внимательно разберитесь в происходящем. Нарисуйте собственную таблицу, а мы вместе ее заполним.
Строка Гитара
Точная формула для вычисления значений в таблице будет приведена позднее, а пока ограничимся общим описанием. Начнем с первой строки.
Строка снабжена пометкой «гитара»; это означает, что вы пытаетесь уложить гитару в рюкзак. В каждой ячейке принимается простое решение: класть гитару в рюкзак или нет? Помните: мы пытаемся найти множество элементов с максимальной стоимостью.
В первой ячейке емкость рюкзака равна 1 фунту. Гитара также весит 1 фунт — значит, она поместится в рюкзак! Итак, стоимость этой ячейки составляет $1500, а в рюкзаке лежит гитара.
Начнем заполнять ячейку.
По тому же принципу каждая ячейка в таблице содержит список всех элементов, которые помещаются в рюкзаке на данный момент.
Посмотрим на следующую ячейку. На этот раз емкость рюкзака составляет 2 фунта. Понятно, что гитара здесь поместится!
Процедура повторяется для остальных ячеек строки. Вспомните, что текущей является первая строка, поэтому выбирать приходится только из одного предмета — гитары. Считайте, что два других предмета пока недоступны.
Возможно, к этому моменту вы слегка сбиты с толку. Почему все это делается для рюкзаков с емкостью 1, 2 и т.д., если в задаче речь идет о рюкзаке с емкостью 4 фунта? Помните, что я говорил ранее? Метод динамического программирования начинает с малых задач, а затем переходит к большой задаче. Вы решаете подзадачи, которые помогут в решении большой задачи. Читайте дальше, и ситуация постепенно прояснится.
После того как первая строка будет заполнена, таблица будет выглядеть так:
Помните, что мы стремимся обеспечить максимальную стоимость предметов в рюкзаке. Эта строка представляет текущую лучшую оценку максимума. Итак, на данный момент из этой строки следует, что для рюкзака с емкостью 4 фунта максимальная стоимость предметов составит $1500.