Page 223 - Bkhargava_-_Grokaem_algoritmy
P. 223
222 Глава 9. Динамическое программирование
предмета. Как решить такую задачу методом динамического программи
рования?
Ответ: никак. В решении, полученном методом динамического програм
мирования, вы либо берете предмет, либо не берете. Алгоритм не преду
сматривает возможность взять половину предмета.
Однако проблема легко решается с помощью жадного алгоритма! Сна
чала вы берете самый ценный предмет - настолько большую его часть,
насколько возможно. Когда самый ценный предмет будет исчерпан, вы
берете максимально возможную часть следующего по ценности предмета
ит.д .
Допустим, вы можете выбирать из следующих товаров.
.
~ f7 е
1
КМ НО А D..M РИС.
.$&/ФУНТ .$~/ФУНТ .$2./ФУНТ
Фунт киноа стоит дороже, чем фунт любого другого товара. А раз так - на
бирайте столько киноа, сколько сможете унести! И если вам удастся набить
им свой рюкзак, то это и будет лучшее из возможных решений.
PIOKJAK
НАБИТ
КИНОА
Если киноа кончится, а в рюкзаке еще остается свободное место, возьмите
следующий по ценности товар и т. д.
www.trk.kg