- Заполняется
- Читается
- Ответ
Задача о размене монет
Даны несколько видов монет. Как заплатить точную сумму как можно меньшим числом монет и сколькими способами это вообще можно сделать? Жадный ответ — сначала самая крупная монета — работает для настоящих денег, но для некоторых наборов монет ошибается. Таблица, которая строит каждую сумму из меньших, всегда дает верный ответ. Нажмите на монету в лотке, чтобы положить ее на прилавок, и на монету на прилавке, чтобы забрать ее обратно. Шкала заполняется по мере приближения к сумме: наберите ее точно, использовав как можно меньше монет. Кнопка «Минимум монет» показывает лучший ответ, а «Жадный» — что получится, если всегда брать самую крупную подходящую монету; это не всегда минимум. Номиналы монет (в центах) и сумму можно изменить на панели. Вид «Таблица» показывает, как динамическое программирование находит минимум монет или считает число способов набрать сумму: нажмите Пуск, чтобы смотреть, как заполняется таблица, или Шаг и Назад, чтобы двигаться по одному шагу, и перетаскивайте ползунок шагов, чтобы перейти в любое место. Каждую монету можно использовать сколько угодно раз. Когда таблица выбрана, клавиши со стрелками делают шаг, пробел запускает и ставит на паузу, а Home и End переходят к началу и к концу.
Как это работает
- Нажимайте на монеты в лотке, чтобы набрать точную сумму, и смотрите, как шкала заполняется в центах.
- Постарайтесь обойтись как можно меньшим числом монет, затем нажмите «Минимум монет» или «Жадный», чтобы сравнить.
- Откройте вид «Таблица» и нажмите Пуск, чтобы увидеть, как каждая ячейка читает меньшую сумму, от которой зависит.
Минимум монет
Для суммы 0 монеты не нужны. Для каждой большей суммы попробуйте каждую монету, которая не больше ее: остаток после этой монеты — меньшая сумма, уже записанная в таблице, поэтому еще одна монета дает кандидата. Наименьший кандидат записывается в клетку, а давшая его монета сохраняется в строке под ней. Когда таблица заполнена, монеты считываются обратно от целевой суммы: возьмите ее последнюю монету, перейдите к оставшейся сумме и повторяйте до 0.
Число способов
Чтобы считать сочетания, а не порядки, таблица добавляет по одной монете в каждой строке. Клетка считает способы составить свою сумму из монет до ее строки включительно: способы без новейшей монеты — это клетка сверху, плюс способы, использующие новейшую монету хотя бы раз, — это клетка в той же строке, левее на столько столбцов, каков номинал монеты. Поскольку монеты добавляются в фиксированном порядке, 1 + 2 и 2 + 1 — один и тот же способ, и он считается один раз.
Часто задаваемые вопросы
Почему жадный метод ошибается?
Жадный метод всегда берет самую крупную подходящую монету и никогда не пересматривает решение. С монетами 1, 3 и 4 и суммой 6 он берет 4, затем 1 и 1: три монеты, хотя хватило бы двух по 3. Для таких систем монет, как евро или доллар США, жадный метод оказывается оптимальным; такие системы называются каноническими.
Чем подсчет способов отличается от подсчета порядков?
При подсчете способов 1 + 2 и 2 + 1 — одно и то же сочетание; при подсчете порядков они считаются отдельно. Приложение считает способы, добавляя монеты по одной строке за раз. Чтобы считать порядки, нужно идти по суммам и для каждой пробовать каждую монету.
Насколько быстр алгоритм размена монет?
Для обеих таблиц число шагов равно числу видов монет, умноженному на сумму. Это быстро для сумм в несколько тысяч, но сумма может быть огромным числом, поэтому, если мерить числом цифр, задача в общем случае NP-трудна.
Что, если сумму нельзя составить?
Ее клетка остается равной ∞, например суммы 1 и 3 с монетами 2 и 5. В режиме Число способов ее значение просто равно 0.
Отправляются ли куда-нибудь данные?
Нет. Все вычисляется в вашем браузере, а ваши последние настройки хранятся в локальном хранилище этого браузера.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Перейти в редактор