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

$1506 Г	$1500 Г
$15-40 Г
*\СоО Г	5*00 Г	ф Ij-oo Г	$3000 М
Ф|5оо Г	$15оо Г	$3.000 н	$3500 Н Г

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


12 3 4



Это означает, что в рюкзак с емкостью 4 фунта можно упаковать товары стоимостью до $3500. И вы полагали, что это итоговый максимум. Но да­вайте добавим новую строку для iPhone.
г
1 ?- 1 4

$1500 ^ Г	$»5оо Г	$»Soo Г	$1566 Г
$\5оО Г	$lsoo г	$15-60 Г	$5»бо М
$■1506 Г	Г	$2000 Н	$3 506 н Г
	,

итара
МАГНИТОФОН НОУТБУК IPHONE
\
НОВЫЙ 0T6ET
Оказывается, в таблице появляется новый максимум! Попробуйте запол­нить последнюю строку, прежде чем читать дальше.
Начнем с первой ячейки. iPhone сам по себе помещается в рюкзак с емко­стью 1 фунт. Старый максимум был равен $1500, но iPhone стоит $2000. Значит, берем iPhone.

$\5оо Г	*»SO6 Г	$1566 Г	$1506 Г
$\50б Г	*\so* г	$1560 Г	$5000 М
$1506 Г	Г	*2066 Н	$35оо Н Г
*2000 I

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


1 7- 3 4

В следующей ячейке можно разместить iPhone и гитару.

*1500 Г	*1500 Г	i\soo Г	*|5оО Г
Г	$1 ГоО г	$1500 Г	*Зо»о АЛ
*\*«о Г	4(5оо Г	f 3.000 н	$3 su> н Г
$3.000 I	$3£оо I Г

Для ячейки 3 ничего лучшего, чем снова взять iPhone вместе с гитарой, все равно не найдется, поэтому оставим этот вариант.
А
О ИЛИ ноутбук+гитара

$2000
IPHONE


МЕСТО 2 НА 3 ФУНТА

вот в последней ячейке ситуация становится более интересной. Текущий максимум равен $3500. Вы снова можете взять iPhone, и у вас еще останется свободное место на 3 фунта.
Но эти 3 фунта можно заполнить на $2000! $2000 от iPhone + $2000 из старой подзадачи: получается $4000. Новый максимум!
Вот как выглядит новая завершающая таблица.

*1500 г	*15оо Г	Hsbo Г	*15оО Г
*1500	*(ГоО	*(*•00	*Зо»о
Г	Г	г	АЛ
*(5*о	41500	*а»оо	*3*оо
Г	Г	^и «Ч	н Г
*35оо	*35оо	+3 $оо	*4000
I	I Г	I Г	I Н

ф
НОВЫЙ ОТВЕТ





Вопрос: может ли значение в столбце уменьшиться? Такое возможно?
12 2 4
П

£15оО	фигой	Ф1500	$\5СЮ
0	0	0	$Зоой

МАКСИМАЛЬНАЯ
стоимость
УМЕНЬШАЕТСЯ 6 ПРОЦЕССЕ V РАБОТЫ

одумайте над ответом, прежде чем продолжить чтение.
Ответ', нет. При каждой итерации сохраняется текущая оценка максимума. Эта оценка ни при каких условиях не может быть меньше предыдущей!
Упражнения
9.1 Предположим, к предметам добавился еще один: МРЗ-плеер. Он весит 1 фунт и стоит $1000. Стоит ли брать его?
Что произойдет при изменении порядка строк?
Изменится ли ответ? Допустим, строки заполняются в другом порядке: магнитофон, ноутбук, гитара. Как будет выглядеть таблица? Заполните таблицу самостоятельно, прежде чем двигаться дальше.
Таблица должна выглядеть гак:
1

0	0	0	*3000 1^м
е!	0	фхооо И \ *	4' $3000 м
*1500 Г	*1500 Г	1 | Фа. ооо Н	X ф35оо н Г

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

2 3 4
Ответ не изменился. Он не зависит от порядка строк.
Можно ли заполнять таблицу по столбцам, а не по строкам?
Попробуйте сами! В данной задаче это ни на что не влияет, но в других за­дачах возможны изменения.
Что произойдет при добавлении меньшего элемента?
Допустим, вы можете выбрать ожерелье, которое весит 0,5 фунта и стоит $1000. Пока структура таблицы предполагает, что все веса являются целы­ми числами. Теперь вы решаете взять ожерелье. Остается еще 3,5 фунта. Какую максимальную стоимость можно разместить в объеме 3,5 фунта? Неизвестно! Вы вычисляли стоимость только для рюкзаков с емкостью 1, 2, 3 и 4 фунта. Теперь придется определять стоимость для рюкзака на

5. 
   фунта.
   

Из-за ожерелья приходится повысить точность представления весов, по­этому таблица должна измениться.
Г
0.5 1 1.5 2 2.5 3 3.5 4



ИТАРА МАГНИТОФОН НОУТБУК ОЖЕРЕЛЬЕ
Можно ли взять часть предмета?
Допустим, вы наполняете рюкзак в продуктовом магазине. Вы можете украсть мешки с чечевицей и рисом. Если весь мешок не помещается, его можно открыть и отсыпать столько, сколько унесете. В этом случае вы уже не действуете по принципу «все или ничего» — можно взять только часть
предмета. Как решить такую задачу методом динамического программи­рования?
Ответ: никак. В решении, полученном методом динамического програм­мирования, вы либо берете предмет, либо не берете. Алгоритм не преду­сматривает возможность взять половину предмета.
Однако проблема легко решается с помощью жадного алгоритма! Сна­чала вы берете самый ценный предмет — настолько большую его часть, насколько возможно. Когда самый ценный предмет будет исчерпан, вы берете максимально возможную часть следующего по ценности предмета ИТ. д.
Д
кинок