Снова классика задач на перебор вариантов — есть номиналы монет, требуется найти все варианты размена указанной суммы. Число монет каждого номинала — не ограничено.
Также в задаче (литкод №518) сказано, что сумма не превышает 5000, а кол-во номиналов для размена не превышает 300.
Брут форс
Допустим, что у нас есть набор монет [1, 2, 5], и нужно найти размен для 5.
Шаг 0. Представим, что мы отслеживаем разменные наборы. В начале у нас есть только один набор, где нет монет — запишем его как [0, 0, 0].
Шаг 1. На следующем шаге добавляем к набору поочередно одну из монет. Так мы получим три новых набора — [1, 0, 0] (сумма 1), [0, 1, 0] (сумма 2) и [0, 0, 1] (сумма 5).
Шаг 2. Один из наборов достиг нужной суммы. Его можно уже не рассматривать далее, а отложить в копилку вариантов размена. Если бы вариант содержал сумму больше требуемой, его можно было бы просто отбросить.
Так у нас останется два набора. С ними вернемся на шаг №1. И будем повторять эти операции, пока у нас есть наборы монет.
К тому моменту в копилке осядут все варианты разменов. Нам нужно отобрать из них уникальные, и их количество будет решением задачи.
Вот реализация этого алгоритма (TypeScript):
|
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 |
// структура описывает набор interface IChange { sum: number // сумма coins: number[] // кол-во для каждой монеты } function change_brute(amount: number, coins: number[]): number { if (amount == 0) return 1; // наборы монет - зададим начальный набор const ch: IChange[] = [ { sum: 0, coins: new Array(coins.length).fill(0) } ]; // копилка результатов // используется MAP, чтобы сразу отсекать дубли const resMap = new Map<string, number[]>(); // пока есть наборы - ищем варианты while (ch.length) { for (let i = ch.length - 1; i >= 0 ; i --) { const cur = ch[i] // каждый набор генерирует еще пачку наборов for (let j = 0; j < coins.length; j ++) { const coin = coins[j]; // отбрасываем варианты с суммой больше чем нужно if (cur.sum + coin > amount) continue; cur.coins[j] ++; if (cur.sum + coin == amount) { // кандидат на новый вариант размена resMap.set(cur.coins.join('.'), [...cur.coins]) } else { // новый набор для рассмотрения ch.push({ sum: cur.sum + coin, coins: [...cur.coins] }) } cur.coins[j] --; } // очередной набор рассмотрен, // удалим его из очереди ch.splice(i, 1); } } // кол-во вариантов в копилке - это ответ return resMap.size }; |
Проблемы подхода очевидны — каждая итерация порождает лавину новых комбинаций. Сами комбинации не являются уникальными, нам приходится их просеивать через Map.
Динамическое программирование
Задача является классическим примером задач на динамическое программирование.
В чем заключается данный подход? Нам требуется ввести индукцию (рекурсию). Т.е. нужно найти решение проблемы через решение более простых случаев.
Рассмотрим ту же задачу — есть монеты [1, 2, 5], нужно найти все способы разменять 5.
Шаг 0. У нас есть полный набор для размена и полная сумма = 5
Шаг 1. Перед нами выбор — использовать первую монету из набора монет для размена или нет. Т.е. задача распадается на две подзадачи
- с использованием текущей монеты, но суммой уменьшенной на номинал монеты;
- без использования текущей монеты (убираем её из набора), но с прежней суммой.
Если сумма равна нулю, то вернем 1 — мы нашли верную комбинацию. Если сумма отрицательная или мы отказались уже от всех монет, то вернем 0.
Решая подзадачи мы снова возвращаемся к шагу 1. Но при этом у нас либо меньше сумма, либо в наборе осталось меньше монет.
Посмотрим реализацию.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
function change_dp(startAmount: number, coins: number[]): number { const nCoin = coins.length // доступные монеты мы отслеживаем индексом в массиве coins (iCoin), // а оставшаяся сумма - это amount const dp = (iCoin: number, amount: number): number => { if (iCoin == nCoin || amount < 0) return 0; if (amount == 0) return 1; if (value !== undefined) return value; value = dp(iCoin + 1, amount) + dp(iCoin, amount - coins[iCoin]) return value; } // шаг 0 - все монеты доступны и используем сумму return dp(0, startAmount) }; |
Сам подход хорош, он также элегантно позволяет избежать проблемы с уникальными комбинациями. Единственное замечание, что вероятно мы будем входить в параметрически эквивалентные ветки рекурсии, потому стоит добавить кеширование.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
function change(amount: number, coins: number[]): number { const nCoin = coins.length const cache = new Map<number, number>(); const dp = (iCoin: number, amount: number): number => { if (iCoin == nCoin || amount < 0) return 0; if (amount == 0) return 1; // ключ стоим, исходя из граничных условий задачи // amount <= 5000 const key = iCoin * 5000 + amount let value = cache.get(key) // если решение уже известно, то вернем результат из кеша if (value !== undefined) return value; value = dp(iCoin + 1, amount) + dp(iCoin, amount - coins[iCoin]) // запоминаем новый результат cache.set(key, value) return value; } return dp(0, amount) }; |
Тут более оптимально использовать массив вместо Map для мемоизации, но принципиально алгоритм от этого не поменяется.