Page 186 - Bkhargava_-_Grokaem_algoritmy

Задача о рюкзаке 185

И так, эти три урока должны проводиться в классе.

~ ct: 30 1() 10: $<) 11 t1:so 12
1 1 1 1 1
'
РМСО&АНМЕ МАТЕМАТИКА МУJЫКА '

Я очень часто слышу, что этот алгоритм подозрительно прост. Он слишком
очевиден, а значит, должен быть неправильным. Но в этом и заключается
красота жадных алгоритмов: они просты! Жадный алгоритм прост: на каж­
дом шаге он выбирает оптимальный вариант. В нашем примере при выборе
урока выбирается тот урок, который завершается раньше других. В техни­
ческой терминологии: на каждом шаге выбирается локально-оптимальное
решение, а в итоге вы получаете глобально-оптимальное решение. Хотите
верьте, хотите нет, но этот простой алгоритм успешно находит оптимальное
решение задачи составления расписания!
Конечно, жадные алгоритмы работают не всегда. Но они так просто реали­
зуются! Рассмотрим другой пример.

Задача о рюкзаке

Представьте, что вы жадный воришка. Вы забрались
в магазин с рюкзаком, и перед вами множество товаров,
которые вы можете украсть. Однако емкость рюкзака
не бесконечна: он выдержит не более 35 фунтов.

Требуется подобрать набор то­
варов максимальной стоимости,
которые можно сложить в рюкзак. Какой алгоритм вы
будете использовать?

И снова жадная стратегия выглядит очень просто:

1. Выбрать самый дорогой предмет, который поместится в рюкзаке.

2. Выбрать следующий по стоимости предмет, который поместится в рюк­
заке ... И так далее.

www.trk.kg