Информатика · объяснение и практика

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

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

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Алгоритм, исполнитель и проверка · Учебная карта

Главная мысль

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

Что означает «лучше» в этой задаче

У нас имеются жетоны положительных целых номиналов, каждого можно брать сколько угодно. Нужно получить заданную неотрицательную целую сумму точно, используя как можно меньше жетонов. Все жетоны имеют одинаковую стоимость как один элемент подсчёта. Это математическая модель разбиения числа, а не рекомендация о реальных деньгах. Если экземпляры ограничены или требуется иная цель, получится уже другой алгоритмический контракт.

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

Один допустимый набор не доказывает минимум

Возьмём номиналы 1, 4 и 6 и целевую сумму 8. Жадный алгоритм сначала берёт 6. Остаток 2 приходится набрать двумя единицами, всего получается три жетона. Однако два жетона номинала 4 тоже дают 8. Одного жетона на эту сумму не существует, поскольку номинала 8 нет. Значит, два — доказанный минимум, а жадный набор проигрывает ему.

Для контрпримера важно проверять обе части: предложенная альтернатива должна быть разрешённой, а её сумма обязана точно совпадать с целью. Нельзя сравнивать набор с превышением цели или незаметно запретить повтор четвёрки. Здесь повторы разрешены с начала. Даже если жадный способ хорошо работает на нескольких предыдущих суммах, этот единственный проверенный проигрыш уже опровергает универсальную гарантию для данной системы.

Пример

Для номиналов 1, 4 и 6 сравним цели 7 и 8. Следует ли из успеха на семи успех на следующей сумме?

Для 7 жадный набор 6+1 использует два жетона, и одним жетоном получить 7 невозможно. Для 8 он использует 6+1+1, хотя 4+4 короче. Успешное решение одной цели не доказывает правильность метода на соседней.

Полный выбор учитывает все возможные последние шаги

Для небольших целых сумм можно хранить M(s), минимальное число жетонов для точной суммы s. База M(0)=0. Для положительной суммы сравнивают значения 1+M(s−c) по всем разрешённым номиналам c не больше s, если остаток достижим. Так учитывается каждый возможный последний жетон. При наличии единицы все неотрицательные целые суммы достижимы; без неё некоторые состояния могут остаться недостижимыми.

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

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

А теперь — вы

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

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

Если найден допустимый набор, задача минимизации уже решена?

Нет. Допустимость подтверждает точную сумму и разрешённые элементы. Оптимальность требует исключить более короткий набор или найти его.

Можно ли отказаться от всех жадных алгоритмов после одного контрпримера?

Нет. Контрпример опровергает конкретную гарантию при конкретных условиях. Для других задач и систем номиналов жадный выбор может быть доказанно правильным.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться