*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 — для гитары и ноутбука.
Возможно, вы подумали, что я воспользовался другой формулой для вычисления стоимости последней ячейки. Это связано с тем, что я опустил некоторые лишние сложности при заполнении предыдущих ячеек. Стоимость каждой ячейки вычисляется по постоянной формуле, которая выглядит так:
П
столстрока бец v *
C6i-Lt'3
МАКСИМУМ
РЕДЫДУЩИЙ МАКСИМУМ ^ЗНАЧЕНИЕ 6 CELL tHJLj})
ИЛИ
г. стоимость текущего элемента +
СТОИМОСТЬ ОСТАВШЕГОСЯ ПРОСТРАНСТВА
CeLL\j-l3Cj -6ЕС ПРЕДМЕТА]
Применяя эту формулу к каждой ячейке таблицы, вы получите такую же таблицу, как у меня. Помните, что я говорил о решении подзадач?
Вы объединили решения двух подзадач для решения еще одной, большей
задачи.
З
IPHoNB Ф-2Й00 1 ФУНТ
адача о рюкзаке: вопросы
Вам все еще кажется, что это какой-то фокус? В этом разделе я отвечу на некоторые часто задаваемые вопросы.
Что произойдет при добавлении элемента?
Представьте, что вы увидели четвертый предмет, который тоже можно засунуть в рюкзак! Вместе со всем предыдущим добром можно также украсть iPhone.
Придется ли пересчитывать все заново с новым предметом? Нет. Напомню, что динамическое программирование последовательно строит решение на основании вашей оценки. К настоящему моменту максимальные стоимости выглядят так:
Do'stlaringiz bilan baham: |