Вася живет в стране Ра, в которой существуют монеты достоинством 1, 4, 5 и 7 ра. Перед Васей стоит задача набора некоторой суммы минимальным числом монет. Он что-то слышал про жадные алгоритмы и решает воспользоваться следующей жадной стратегией: пока возможно, набирать сумму наиболее крупными монетами.

1. Эта стратегия оптимальна, то есть дает минимальное возможное число монет. 1 балл

Верно

Неверно

2. Подумайте, к какой из уже известных вам задач проще всего свести данную задачу? 1 балл

К задаче топологической сортировки

К задаче поиска кратчайшего пути

К задаче о разбиении

К задаче о планировании встреч

К задаче коммивояжера