Page 227 - Bkhargava_-_Grokaem_algoritmy

226 Глава 9. Динамическое программирование

Возможно ли, что при лучшем решении в рюкзаке
остается пустое место?

Да. Представьте, что вы можете также положить
\ \ 1 1
' в рюкзак бриллиант.
Бриллиант очень крупный: он весит 3,5 фунта
и стоит 1 миллион долларов - намного больше, чем
любые другие предметы. Безусловно, нужно брать
БРИ/\ЛИ~НТ.
СТОИМОСТЬ 11 ООО ООО , именно его! Но в рюкзаке остается еще пустое место
&Е.С ~.5 ФУНП на О,S'фунта, и в нем ничего не поместится.

Упражнения

9.2 Предположим, что вы собираетесь в турпоход. Емкость вашего рюк­
зака составляет 6 фунтов, и вы можете взять предметы из следующего
списка. У каждого предмета имеется стоимость; чем она выше, тем
важнее предмет :

Q вода, 3 фунта, 1 О;
Q книга, 1 фунт, 3;

Q еда, 2 фунта, 9;

Q куртка, 2 фунта, 5;

Q камера, 1 фунт, 6
Как выглядит оптимальный набор предметов для похода?

Самая длинная общая подстрока

Мы рассмотрели одну задачу динамического про­
граммирования. Какие выводы из нее можно сде­
лать?

Q Динамическое программирование применяется
для оптимизации какой-либо характеристики

www.trk.kg