Решение этой задачи зависит от некоторых входных условий. Если в нашем распоряжении монеты определенного номинала, то мы можем свести решение к последовательному делению суммы сдачи на все возможные номиналы, начиная с самого большого.
Если вы не забыли, задача состоит в том, чтобы найти минимальное количество монет, чтобы выдать сдачу. Оформлять варианты будем в такую или похожую функцию. Первым аргументом присылаем массив номиналов, а вторым сумму сдачи.
Фрагмент 2.53
static int GetChange(int[] values, int change)
{
...
}Решение на основе деления
Мы можем отсортировать номиналы от большего к меньшему и начать делить сумму сдачи на все значения по очереди, а результат деления каждый раз приплюсовывать к какой-то переменной. По сути, результат деления суммы сдачи на номинал указывает на то, сколько монет мы сможем выдать. Но также может возникать остаток от деления, его мы присваиваем в сумму сдачи. И делим на следующий номинал. Так, постепенно, мы придем к какому-нибудь ответу.
Полностью решение представлено ниже.
Фрагмент 2.54
static int GetChangeSimple(int[] values, int change)
{
int count = 0;
foreach(int value in values.Distinct().OrderByDescending(x => x))
{
count += change / value;
change = change % value;
if (change == 0) return count;
}
return 0;
}Как вы видите оно очень простое, а благодаря LINQ его удалось записать в 6 строчек. Но решает ли оно нашу задачу? Да, если номиналы подчиняются определённому правилу. Так, в случае если у нас номиналы {1, 5, 10, 15, 20} и сумма сдачи скажем 50, то всё правильно, он нам сообщит о том, что нужно 3 монеты: 20+20+10.
Но что будет, если номиналы мы зададим как {1, 5, 10, 15, 17, 20}, а сумму сдачи как 34. Сюрприз-сюрприз, алгоритм насчитал 6 монет: 20 + 10 + 1 + 1 + 1 + 1. Так ли это? Нет, сдачу можно выдать двумя монетами: 17 + 17. В чём проблема алгоритма? В том, что он работает жадным методом.
При решение задачи, в таких условиях, выдача сдачи монетами номиналом в 20 может выглядеть хорошо, но это отрежет нам более оптимальный путь решения. В результате, этот алгоритм не самый универсальный и мы попробуем придумать кое-что по-лучше.
Рекурсивное решение
Более совершенный алгоритм будет строиться, по-сути, на основе перебора. Мы будем анализировать разные пути размена до тех пор, пока не найдём оптимальный.
Рекуррентное соотношение можно записать так:
Мы определили функцию, которая работает с неким множеством S, которое в нашем случае является набором доступных номиналов. На входе эта функция получает информацию о том, сдачу для какой суммы нужно дать, а её результатом является количество монет.
Если сумма сдачи может быть дана одной монетой, то возвращаем единицу. Это базовый случай и он не требует дальнейшего вычисления. Делается это через проверку принадлежности n множеству S (сумма сдачи равняется одному из номиналов монет).
Если мы не можем дать сдачу одной монетой, то мы начинаем впадать в рекурсию. Мы берём каждый номинал и отнимаем его от текущей сдачи и вызываем функцию с получившимся значением. А к результату прибавляем единицу. В результате у нас будет множество количества монет для сдачи, если мы начнем выдачу с определенного номинала и нам нужно взять минимальное значение.
Предположим что S = { 1, 5, 10, 15, 17, 20 }.
И мы вызовем функцию со значением 34.
В таком случае, мы получим в первом шаге вызовы следующих функций:
F(33), F(29), F(24), F(19), F(17), F(14). Каждый из этих вызовов приведёт ещё к 6 вызовам и т.д. В результате получится огромный граф вариантов сдачи. Кратчайший путь от самого верха до базового случая (точки, где мы получим ноль) и есть ответ. Этот путь вычисляет по ходу дела.
Давайте посмотрим на реализацию.
Фрагмент 2.55
static int GetChange(int[] values, int change)
{
int minCoins = change;
if (values.Contains(minCoins))
{
return 1;
}
else
{
foreach (var value in values.Where(x => x <= change))
{
int numCoins = 1 + GetChange(values, change - value);
if(numCoins < minCoins)
{
minCoins = numCoins;
}
}
return minCoins;
}
}Данный алгоритм более гибкий и надёжный. Но, как вы уже поняли, он не адекватен с точки зрения ресурсов. Очень быстро граф разрастается до немыслимых размеров и мы уже не можем быстро найти правильный ответ. И, как вы уже догадались, мы попробуем применять динамическое программирование для решения задачи.
Рекурсивное решение – оптимизация на основе мемоизации
Если ещё раз посмотреть на граф выполнения выше, мы обнаружим что очень часто мы прибегаем к повторному расчёт сдачи одних и тех же сум. Это отрицательно сказывается на скорости выполнения, и мы можем прямо сейчас применить технику мемоизации и просто запомнить решения подзадач.
Давай рассмотрим реализацию.
Фрагмент 2.56
static int GetChangeMemoization(int[] values, int change, int[] getChangeResults)
{
int minCoins = change;
if (values.Contains(minCoins))
{
getChangeResults[change] = 1;
return 1;
}
else if (getChangeResults[change] != 0)
{
return getChangeResults[change];
}
else
{
foreach (var value in values.Where(x => x <= change))
{
int numCoins = 1 + GetChangeMemoization(values, change - value);
if (numCoins < minCoins)
{
minCoins = numCoins;
getChangeResults[change] = minCoins;
}
}
}
return minCoins;
}Мы не сделали ничего выдающегося, просто запомнили предыдущие решения. Но алгоритм уже стал гораздо более резвым, и при увеличение числа сдачи он уже не уходит в очень долгие раздумья.
Рекурсивное решение – оптимизация на основе табуляции
Как было описано раньше, этот подход оптимизации заключается в том, что мы заранее решаем подзадачи. Мы заполняем таблицу результатов с самого начала до нужной суммы.
Каждый раз мы работаем с некой суммой N и пытаемся найти решение для неё. Для этой N мы смотрим: если взять некое предыдущее решение для N минус номинал доступной монеты, то не будет ли решение, полученное на основе него, (к тому решению мы добавим 1, что означает добавление монеты этого номинала) более оптимальным? Если да, то для N мы выбираем именно его.
Давайте посмотрим пошаговую работу алгоритма. Зададим номиналы как { 1, 5, 7, 10}. А сумму сдачи, равную 14. При запуске список результатов будет такой.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Сверху – сумма сдачи, снизу – количество монет.
Далее рассмотрим пошагово как алгоритм заполнит таблицу.
1) Сдачу, суммой в 1, мы можем дать одной монетой, номиналом в 1.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2) Сдачу, суммой в 2, мы можем дать двумя монетами, номиналом в 1.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
3) Сдачу, суммой в 3, мы можем дать тремя монетами, номиналом в 1.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
4) Сдачу, суммой в 4, мы можем дать четырьмя монетами, номиналом в 1
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
5) И вот тут начинается самое интересное. Находясь в сумме 5, мы имеем в распоряжении уже две монеты, номиналом в 1 и 5. Мы проверяем два решения: посмотрев на решение суммы 5 – 1 монеты, получаем 4 и на сумму 5-5, получаем ноль. Ноль меньше четырёх, поэтому мы используем его + 1 монета. И получаем решение в 1 монету.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
6) Здесь мы проделываем тот же трюк, только приходим к тому, что решение для суммы, меньше нашей на монету, номиналом 1, нам подходит больше.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 1 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
7)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 1 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
8)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 1 | 2 | 1 | 2 | 0 | 0 | 0 | 0 | 0 | 0 |
9)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 1 | 2 | 1 | 2 | 3 | 0 | 0 | 0 | 0 | 0 |
10)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 1 | 2 | 1 | 2 | 3 | 1 | 0 | 0 | 0 | 0 |
11)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 1 | 2 | 1 | 2 | 3 | 1 | 2 | 0 | 0 | 0 |
12)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 1 | 2 | 1 | 2 | 3 | 1 | 2 | 3 | 0 | 0 |
13)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 1 | 2 | 1 | 2 | 3 | 1 | 2 | 3 | 4 | 0 |
14)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 1 | 2 | 3 | 4 | 1 | 2 | 1 | 2 | 3 | 1 | 2 | 3 | 4 | 1 |
И полная реализация алгоритма.
Фрагмент 2.57
static int GetChangeTabulization(int[] values, int change, int[] getChangeResults)
{
for(int cents = 0; cents < change+1; cents++)
{
int coinsCounts = cents;
foreach (var value in values.Where(value => value <= cents))
{
if(getChangeResults[cents-value] + 1 < coinsCounts)
{
coinsCounts = getChangeResults[cents - value] + 1;
}
}
getChangeResults[cents] = coinsCounts;
}
return getChangeResults[change];
}