Дана сумма amount и номиналы монет. Требуется разменять сумму минимальным набором монет.
Если рассматривать набор монет, который используется в реальной жизни, т.е. [1коп, 5коп, 10коп, 50коп, 1р, 2р, 5р, 10р], то во-первых, решение всегда существует, т.к. мы может взять всю сумму по 1 копейке, а во-вторых, можно применить быстро сходящийся, т.н. «жадный алгоритм».
Жадный алгоритм
Логика будет простой — вы начинаете с монет самого большого достоинства и, пока это возможно, уменьшаете сумму за счет них. Когда остаток суммы становится меньше вашей крупной монеты, вы выбираете монету поменьше достоинством и повторяете описанные выше действия.
Реализация на JS(TS):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
// coins - массив номиналов монет, // amount - сумма денег, подлежащих размену function coinChangeGreedy(coins: number[], amount: number): number { // отсортируем от больших к меньшим номиналы монет coins.sort((a,b) => b - a); // считаем монеты let count = 0; let coinIndex = 0; while (coinIndex < coins.length) { const coinValue = coins[coinIndex]; if (coinValue <= amount) { // добавим монеты выбранного достоинства в копилку count += (amount - amount % coinValue) / coinValue; // пересчитаем сумму оставшихся денег amount = amount % coinValue; } // следующий номинал coinIndex ++; } // если не удалось выбрать всю сумму до нуля вернем -1 // такое возможно, если номинал самой мелкой монеты больше единицы if (amount !== 0) return -1; return count; }; |
Такой алгоритм не даст желаемого результата (т.е. минимального числа монет) или вообще не найдет решения для произвольного набора монет. Область его применимости ограничивается набором монет, где каждый следующий номинал кратен предыдущему или составлен из суммы двух предыдущих номиналов (50 коп = 10 коп x5, а 5р = 2р * 2 + 1р).
Например, для [7, 8] и суммы 30, функция выдаст -1, хотя довольно очевидно, что можно взять две монеты по 8 и две монеты по 7, чтобы разменять требуемую сумму.
Рекурсия
Старая добрая рекурсия или динамический алгоритм.
Возьмем другой пример — набор монет [1, 4, 6] и сумма 8. Жадный алгоритм выдаст нам результат 3 — 6×1, 1×2, хотя более оптимально взять 2 монеты номиналом 4.
Рекурсивный же алгоритм отработает правильно, т.к. будет перебирать все возможные варианты.
Логика в рекурсии будет следующая: на каждом шаге вы стоите перед выбором — начать пользоваться монетами другого номинала или использовать одну монету выбранного номинала.
Нас интересует минимум монет, потому мы сравним оба результата и оставляем тот, что требует меньше монет.
Давайте рассмотрим пример реализации. Я написал его на JS/TS и мне было интересно выводить не только общее кол-во монет, но и кол-во каждой из монет
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
// тип данных ICoins interface ICoins { n: number, // общее кол-во монет coins: number[] // кол-во монет каждого номинала } // coins - массив номиналов монет, // amount - сумма денег, подлежащих размену function coinChangeRecurse(coins: number[], amount: number): number { const len = coins.length; const MAX = Number.MAX_SAFE_INTEGER; // сортировка набора монет не обязательна, // но как показали вычисления ускоряет сходимость coins.sort((a,b) => a - b); // эта допфункция просто складывает два объекта типа ICoins // также учитывает кейс с состоянием ICoins, которое // описывает неразрешимые ситуации // тогда n (число монет) принимает значение Number.MAX_SAFE_INTEGER const sumOfIcons = (c1: ICoins, c2: ICoins): ICoins => { const result = { n: c1.n !== MAX && c2.n !== MAX ? c1.n + c2.n : MAX, coins: Array(len).fill(0) } if (result.n !== MAX) { result.coins.forEach((elm, index) => { result.coins[index] = c1.coins[index] + c2.coins[index] ; }) } return result; } // рекурсия // на входе amount - остаток суммы, который надо разменять // index - номер монеты в массиве coins const find = (amount: number, index: number): ICoins => { // так как мы двигаемся от большего номинала к меньшему // то имеет смысл проверить не делится сумма нацело на // очередной номинал монеты if (amount % coins[index] === 0) { const n = amount / coins[index]; const c = Array(len).fill(0); c[index] = n; // вернем n монет текущего номинала return { n, coins: c }; } else if (index === 0) { // если остаток нацело делится на меньший номинал, // то мы уже вернули результат в ветвлении выше, // если этого не произошло, то размен не удался // вернем состояние ошибки return { n: MAX, coins: [] }; } // здесь мы берем размен со следующим по списку номиналом const nextChange = find(amount, index - 1); let t:ICoins = { n: MAX, coins: [] }; if (coins[index] <= amount) { const one = {n: 1, coins: Array(len).fill(0) } one.coins[index] ++; // берем 1 монету текущего номинала t = sumOfIcons(one, find(amount - coins[index], index)); } // вернем тот результат, что требует меньше монет return nextChange.n < t.n ? nextChange : t; } // вызов рекурсии const result = find(amount, len - 1); // выводим результат размена console.log(coins, result); // возвращаем кол-во монет return result.n === MAX ? -1 : result.n; }; |
Случай, где мы откладываем по одной монете, сильно ограничивает нас в размерах суммы, которую мы можем разменять за приемлемое время. Также сильно влияет на время и размер набора монет. Т.е. область применения алгоритма довольно узка.
Зато можно получить размен для таких экзотических случаев как [55, 56, 57] и 1000:
|
1 2 |
// пример результат работы: [ 55, 56, 57 ] { n: 18, coins: [ 13, 0, 5 ] } |
Проблему быстродействия можно попробовать решить, применяя гибридный алгоритм.
Гибридный алгоритм
Он также использует рекурсивные вычисления, но в форме накопления итога. Я не стал его загромождать подсчетом номинала отдельных монет и оптимизировать, чтобы более внятно пояснить суть.
Для нахождения минимально требуемого кол-ва монет, мы строим таблицу. Каждая строка соответствует своему номиналу монет, а по столбцам у нас разворачивается весь диапазон суммы размена [0 … amount].
Т.е. таблица, как вы понимаете, очень большая. Тем не менее, размер amount и набор номиналов тут могут быть гораздо больше, чем в рекурсивной реализации, а сложность вычислений будет расти лишь линейно.
Что же мы вычисляем в этой большой матрице? Рассмотрим кейс [3, 8, 9] и сумму 16.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | … | 15 | 16 | |
| 3 | 0 | ||||||||||
| 8 | 0 | ||||||||||
| 9 | 0 |
Логика следующая — мы начинаем с наименьшей монеты (индекс j) и идем вдоль строки таблицы увеличивая сумму (индекс i). Каждый раз мы вычисляем (если это возможно), сколько монет требуется чтобы разменять сумму i.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | … | 15 | 16 | |
| 3 | 0 | — | — | 1 | — | — | 2 | — | 5 | — | |
| 8 | 0 | ||||||||||
| 9 | 0 |
Вычисляется каждая ячейка так: берем минимум двух значений — 1) результат из строки j-1 (если она есть), и 2) — значение для того же номинала, но для [j][i — [номинал монеты]] + 1.
Для монеты 3 предыдущей строки нет, потому мы имеем только кратные трем значения в соответствующих столбцах. Технически, значение для [i][3] получено как = i[0] + 1, а не просто i % 3.
Для 8ки, к примеру, [j][14], получается так — значения на предыдущей строке нет, а на текущей составляет [j][14-8] + 1, туда попала двойка из предыдущей строки. Мы как бы к двум монетам по 3 добавили монету на 8, и так разложили 14.
| 0 | 1 | 2 | 3 | … | 6 | 7 | 8 | 9 | … | 14 | 15 | 16 | |
| 3 | 0 | — | — | 1 | … | 2 | — | — | 3 | … | — | 5 | — |
| 8 | 0 | — | — | 1 | … | 2 | — | 1 | 3 | … | 3 | 5 | 2 |
| 9 | 0 | … | … |
Так возникает рекурсивная связь между строками и, так как мы выбираем каждый раз минимум из двух пар значений, то получаем каждый раз оптимальное кол-во монет для размена суммы i.
Конечным результатом становится значение в правом нижнем углу таблицы.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
function coinChange(coins: number[], amount: number): number { const len = coins.length; const MAX = Number.MAX_SAFE_INTEGER; // матрица для расчета const t: number[][] = []; // заполним её значением MAX, кроме столбца 0 // где проставим нули. for (let j = 0; j < len; j ++) { t[j] = Array(amount + 1).fill(MAX); t[j][0] = 0; } for (let j = 0; j < len; j ++) { // значение очередного делителя const del = coins[j]; for (let i = 1; i <= amount; i ++) { // opt1 и opt2 - это два числа, из которых мы // будем выбирать минимум // opt1 - это значение с предыдущей строки const opt1 = j > 0 ? t[j - 1][i] : MAX; if (i >= del) { // пока i не станет >= делителя, то // у нас нет доступного значения opt2 const opt2 = t[j][i - del] + 1; t[j][i] = opt1 > opt2 ? opt2 : opt1; } else { t[j][i] = opt1; } } } const result = t[len - 1][amount] // результат из нижнего-правого угла таблицы return result === MAX ? -1 : result; } |
Расходы памяти можно сократить до двух строк, так как для вычисления следующей строки нам нужна только предыдущая строка.