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

*1S-oo —i. £	* 1500 1 Q
*1500 Г
ЧУ *1 S°° Г	4- *|5»о Г		*1500 Г

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

Магнитофон все равно не помещается, так что оценка остается неизменной.

А если емкость рюкзака увеличивается до 4 фунтов? Ага, магнитофон наконец-то войдет в рюкзак! Старая максимальная стоимость была равна $1500, но если вместо гитары положить магнитофон, она увеличится до $3000! Берем магнитофон.

1	2	3	4
	*15-оо -jT.	*\5<> о —	*1500 Г
А *15-00 Г	4- *|5оо Г	*1500 Г	"*3ооо. ‘ м
!

ГИТАРА
МАГНИТОФОН

Оценка только что обновилась! Имея рюкзак емкостью 4 фунта, вы можете положить в него товары стоимостью по крайней мере $3000. Из таблицы видно, что оценка постепенно возрастает.

	1	2	3	4
ГИТАРА	*1500 «X	*15-00 —Л?	*■15*0	*ISoO Г
МАГНИТОФОН	*15-0° Г	*• *15<>^а Г	«г *1500 Г	ys Зооо t " ' ' М
НОУТБУК

СТАРАЯ ОЦЕНКА НОВАЯ ОЦЕНКА
ИТОГОВОЕ РЕШЕНИЕ



Ноутбук
А теперь проделаем то же для ноутбука! Ноутбук весит 3 фунта, поэтому он не поместится в рюкзак с емкостью 1 или 2 фунта. Оценка для первых двух ячеек остается на уровне $1500.

	1	Z	3	4
	*\5оО	$\5сю	*1500	1 *>5оо
ГИТАРА	| г	1 ^Г	11^г	Г
МАГНИТОФОН	Ч' *\so о 1 г	*1*оо _|Л	4- *isoo Г	ФЗооо М
НОУТБУК	4 ilsroo Г	*\se>0 Г

Для 3 фунтов старая оценка составляла $1500. Но теперь вы можете вы­брать ноутбук, который стоит $2000. Следовательно, новая максимальная оценка равна $2000!

	1	г	3	4
ГИТАРА	*«оо | г	$\SOO 1^г	*1500 , ^Г	*1500 Г
МАГНИТОФОН	Ч' *\$ьо 1 Г	*1500	4- *1500 г	фЗооо М
НОУТБУК	ОО	i\SO0	% * ‘ ' ✓ fcZooo.
	г	Г	' н

При 4 фунтах ситуация становится по-настоящему интересной. Это очень важная часть. В настоящее время оценка составляет $3000. В рюкзак можно положить ноутбук, но он стоит всего $2000.$3ооо ИЛИ $2ооо

МАГНИТОФОН НОУТБУК
Т
$ 3ооо
МАГНИТОФОН


ИЛИ


$2000 4- _?_?
НОУТБУК


СВОБОДНОЕ
МЕСТО
НА 1 ФУНТ

ак-так, старая оценка была лучше. Но постойте! Ноутбук весит всего 3 фунта, так что 1 фунт еще свободен! На это место можно еще что-нибудь положить.
Какую максимальную стоимость можно разместить в 1 фунте? Да вы же уже вычислили ее!

	1	2	3	4-
	i\soo		iMSOb	$1500
	| ^г		i_L	г
	i\s оо	*tsoo	ф $»SOO	$3ooo
	.^г	l—L	г	м
	V- *1ГОО Г	Г	fcZooo- / \ ' и

В
$3000 ИЛИ

МАГНИТОФОН



2ооо 4_
НОУТБУК


соответствии с последней оценкой в свободном месте емкостью в 1 фунт можно разместить гитару стоимостью $1500. Следовательно, настоящее сравнение выглядит так:
Вы удивлялись, зачем мы вычисляем максимальную стоимость для рюк­заков меньшей емкости? Надеюсь, теперь все стало на свои места! Если в рюкзаке остается свободное место, вы можете использовать ответы на эти подзадачи для определения того, чем заполнить это пространство. Вместо магнитофона лучше взять ноутбук + гитару за $3500.
В завершающем состоянии таблица выглядит так:

1	2	3	4
*15о» 1^Г	. ^г	♦•500 , ^Г	*1500 Г
$) SCO	—* -Alsoo ~ 4.^г:	Ф А1500 Г_	i^ooo -v м
	*1500	*5.000	*?5оо;
Г	Г		н Г

ГИТЛРА
МАГНИТОФОН
НОУТБУК


*
OT6ET1

Итак, мы получили ответ: максимальная стоимость товаров, которые по­местятся в рюкзак, равна $3500 — для гитары и ноутбука.

Возможно, вы подумали, что я воспользовался другой формулой для вычисления стоимости последней ячейки. Это связано с тем, что я опу­стил некоторые лишние сложности при заполнении предыдущих ячеек. Стоимость каждой ячейки вычисляется по постоянной формуле, которая выглядит так:

1. 
   П
   стол­строка бец v *
   C6i-Lt'3
   
   МАКСИМУМ
   РЕДЫДУЩИЙ МАКСИМУМ ^ЗНАЧЕНИЕ 6 CELL tHJLj})
   

ИЛИ
г. стоимость текущего элемента +
СТОИМОСТЬ ОСТАВШЕГОСЯ ПРОСТРАНСТВА
CeLL\j-l3Cj -6ЕС ПРЕДМЕТА]
Применяя эту формулу к каждой ячейке таблицы, вы получите такую же таблицу, как у меня. Помните, что я говорил о решении подзадач?
Вы объединили решения двух подзадач для решения еще одной, большей
задачи.

З
IPHoNB Ф-2Й00 1 ФУНТ

адача о рюкзаке: вопросы
Вам все еще кажется, что это какой-то фокус? В этом раз­деле я отвечу на некоторые часто задаваемые вопросы.
Что произойдет при добавлении элемента?
Представьте, что вы увидели четвертый предмет, который тоже можно за­сунуть в рюкзак! Вместе со всем предыдущим добром можно также украсть iPhone.
Придется ли пересчитывать все заново с новым предметом? Нет. Напомню, что динамическое программирование последовательно строит решение на основании вашей оценки. К настоящему моменту максимальные стоимости выглядят так:

*1 st>o Г