Page 226 - Bkhargava_-_Grokaem_algoritmy

Упражнения 225

последующий элемент займет всего один день. Следовательно, потребуется
1 день на каждую достопримечательность + 1 день на переезды = 3,5 дня,
а не 4,5.
Если вы положите Эйфелеву башню в свой «рюкзак~, то Лувр станет «де­
шевле~> - он займет всего 1 день вместо 1,5 дня. Как смоделировать это
обстоятельство в динамическом программировании?

Никак. Динамическое программирование - мощный метод, способный ре­
шать подзадачи и использовать полученные ответы для решения большой
задачи. Динамическое программирование работает толъко в том случае,
если каждая подзадача автономна, то естъ не зависит от других подзадач.
Из этого следует, что учесть поездки в Париж в алгоритме динамического
программирования не удастся.

Может ли оказаться, что решение требует

более двух «nодрюкзаков»?

Может оказаться, что в лучшем решении должны отбираться больше двух
элементов. В текущем варианте алгоритма объединяются не более двух
«подрюкзаков~> - больше двух их не бывает. Однако вполне возможно, что
у этих «подрюкзаков~ будут собственные «подрюкзаки~.

1-\0 МОГУТ БЫТЬ •ПOJI.­
TPE)I. •ПOJI.PIOKJAKO&" PIOKJAKИ", КОТОРЫЕ.
БЫТЬ НЕ. мо~п
COJI.EP~AТ СОБСТ&ЕН­
НЫЕ. •ПOJl.PIOKJAKИ"

www.trk.kg