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

В этой главе
Вы освоите динамическое программирование — метод решения сложных задач, разбиваемых на подзадачи, которые решаются в первую очередь.
✓ Рассматриваются примеры, которые научат вас искать решения новых задач, основанные на методе динами­ческого программирования.


Задача о рюкзаке


Вернемся к задаче о рюкзаке из главы 8. У вас есть рюкзак, в котором можно унести товары общим весом до 4 фунтов.

рограммирование

Е
МАГНИТОФОН МФФФ 4- ФУНТА


НОУТБУК
ЦфФф
5 ФУНТА


ГИТАРА


1 ФУНТ

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

	- X	X
	1 МАГНИТО- |	ГИТАРА
j ГИТАРА	ФОН	-г
I 4-	- 1 +	МАГНИТОФОН
" \ноутбук У	V НОУТБУК /	ЧНОУТБУК j

ГИТАРА
■‘г
МАГНИТО-


'Хне помещается ^_ие помещается


г
МАКСИМАЛЬНАЯ
СТОИМОСТЬ

^ФОН
X НЕ ПОМЕЩАЕТСЯ 435^0
Такое решение работает, но очень медленно. Для 3 предметов приходится обработать 8 возможных множеств, для 4 — 16 и т. д. С каждым добавляе­мым предметом количество множеств удваивается! Этот алгоритм выпол­няется за время 0(2^Лп), что очень, очень медленно.
3
4- ПРЕДМЕТА:
1 6
ВОЗМОЖНЫХ
МНОЖЕСТВ


5 ПРЕДМЕТОВ:
ВОЗМОЖНЫХ
МНОЖЕСТВА

ПРЕДМЕТА:
FTO
возможных
МНОЖЕСТВ
Для любого сколько-нибудь значительного количества предметов это не­приемлемо. В главе 8 вы видели, как вычисляются приближенные решения. Такие решения близки к оптимальным, но могут не совпадать с ними.
Как же вычислить оптимальное решение?
Динамическое программирование
Ответ: с помощью динамического программирования! Давайте посмотрим, как работает этот метод. Процедура начинается с решения подзадач с по­степенным переходом к решению полной задачи.
В
задаче о рюкзаке начать следует с реше­ния задачи для меньшего рюкзака (или «подрюкзака»), а потом на этой основе попытаться решить исходную задачу.
Динамическое программирование — до­статочно сложная концепция; не огор­чайтесь, если после первого прочтения что-то останется непонятным. При­меры помогут вам разобраться в теме.
Для начала я покажу вам алгоритм в действии. После этого у вас наверняка появится много вопросов! Я постараюсь ответить на них.
Каждый алгоритм динамического программирования начинается с табли­цы. Вот как выглядит таблица для задачи о рюкзаке.
СТОЛБЦЫ ПРЕДСТАШЮТ РАЗААЕРЫ РЮКЗАКА ОТ 1 ДО 4 ФУНТ06
1
ПО ОДНОЙ СТРОКЕ ДЛЯ
КАЖДОГО
ПРЕДМЕТА


2 3
Строки таблицы представляют предметы, а столбцы — емкость рюкзака от 1 до 4 фунтов. Все эти столбцы нужны, потому что они упрощают вычис­ление стоимостей «подрюкзаков».
В исходном состоянии таблица пуста. Нам предстоит заполнить каждую ячейку таблицы. После того как таблица будет заполнена, вы получите от­вет на свою задачу. Пожалуйста, внимательно разберитесь в происходящем. Нарисуйте собственную таблицу, а мы вместе ее заполним.
Строка Гитара
Точная формула для вычисления значений в таблице будет приведена позднее, а пока ограничимся общим описанием. Начнем с первой строки.
12 3 4
ГИТАРА
МАГНИТОФОН
Строка снабжена пометкой «гитара»; это означает, что вы пытаетесь уло­жить гитару в рюкзак. В каждой ячейке принимается простое решение: класть гитару в рюкзак или нет? Помните: мы пытаемся найти множество элементов с максимальной стоимостью.
В первой ячейке емкость рюкзака равна 1 фунту. Гитара также весит 1 фунт — значит, она поместится в рюкзак! Итак, стоимость этой ячейки составляет $1500, а в рюкзаке лежит гитара.
Начнем заполнять ячейку.

	1	2	2	4
ГИТАРА	$iSoo Г
МАГНИТОФОН
НОУТБУК

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

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

$15оо Г	*\50О Г

ГИТАРА__МАГНИТОФОН__НОУТБУК'>ГИТАРА
МАГНИТОФОН
НОУТБУК


1 2 3 4



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

$ISOO Г	*1500 Г	$\5оо Г	*1500 Г

гитара
МАГНИТОФОН
НОУТБУК

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

П
Помните, что мы стремимся обеспечить максимальную стоимость пред­метов в рюкзаке. Эта строка представляет текущую лучшую оценку мак­симума. Итак, на данный момент из этой строки следует, что для рюкзака с емкостью 4 фунта максимальная стоимость предметов составит $1500.
1 7 2 4
-*• ■*- Lit III! TCkVIllie


ГИТАРА


МАГНИТОФОН


$1500
Г


*1500
Г


$1500
Г


*1500
Г


НИША I С1\ГЦПЛ
ОЦЕНКА ТОГО, ЧТО СЛЕДУЕТ КРАСТЬ: ГИТАРУ ЗА $1500

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

	1	2	2	4
ГИТАРА	$(5оо Г	*1500 Г	$1500 Г	*1500 Г
МАГНИТОФОН
НОУТБУК

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

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

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

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

	1	2	3	A
ГИТАРА	*1500 _xU	*ISOO Г	iisoo Г	^ISoo г
МАГНИТОФОН	sT *1500 Г
НОУТБУК

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

1 2		3		4
*15о» __4_I