Вопрос 2 из 2

Практика: алгоритм, исполнитель и проверка

Жадный выбор монет: когда самый крупный номинал не даёт минимум

От чтения к действию

А теперь — вы

Номиналы жетонов 1, 5 и 8, повторы разрешены. Нужно получить сумму 10 минимальным числом жетонов. Как соотносятся жадный выбор самого крупного подходящего и оптимум?

Разберёмся в теме

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

Объяснение и примеры

Частые вопросы

Где найти подробное решение?

Перейдите по ссылке «Объяснение и примеры» над этим блоком. Там разобрана тема текущего вопроса.

Можно ли попробовать снова?

Да. После проверки можно изменить ответ. Переход к следующему вопросу не блокируется результатом, а личный счёт не сохраняется.