Решаем задачу № 2218 с leetcode — Maximum Value of K Coins From Piles.
В названии фигурирует слова монеты и стопки. Если представить себе, что монеты могут быть произвольного номинала, то да — суть именно такая. У нас есть стопки монет, и дано число операций, за каждую из которых, мы можем взять монету из произвольной кучи.
Нужно вернуть максимальную сумму, которую возможно набрать при таких условиях.
Решение «в лоб»
Первый заход попробуем реализовать грубой силой. Представьте себе следующую рекурсию:
- Выбираем любую стопку и берем от туда «монету».
- Перебираем все стопки монет.
- Результат шага — это лучшая сумма = взятая монета + очередной шаг рекурсии. Где мы должны решить задачу для K — 1 операций, зная о числе оставшихся монет в кучах.
- Если число операции на очередном шаге равно нулю мы возвращаем ноль, т.к. больше монет мы брать не можем.
Основная проблема — в затратах на описание очередного шага рекурсии. Число оставшихся монет — это массив, который указывает сколько монет было взято в каждой куче.
|
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 |
function maxValueOfCoins(piles: number[][], k: number): number { const N = piles.length; const iter = (coins: number[], k: number): number => { if (k == 0) return 0; // в цикле берем монету из каждой кучи по очереди // и таким образом переходим к следующему шагу рекурсии, // на котором у нас уже k - 1 операций let best = 0 for (let i = 0; i < piles.length; i ++) { if (piles[i].length > coins[i]) { // создаём описание кол-ва взятых монет const nextCoins = [...coins] nextCoins[i] ++ const nextRes = piles[i][coins[i]] + iter(nextCoins, k - 1) if (nextRes > best) best = nextRes; } } return best; } // в начале у нас взято 0 монет из любой кучи, // а осталось k операций const res = iter(new Array(N).fill(0), k) return res }; |
Этот цикл длится буквально бесконечность для совсем не больших наборов монет и числа операций. Чтобы как то улучшить ситуацию, мы можем кешировать рекурсию. Состояние целиком описывается вектором coins — числом взятых монет из определенных куч.
Сериализуем массив, чтобы получить одномерный ключ для кеша. Вот, что получилось:
|
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 |
function maxValueOfCoins(piles: number[][], k: number): number { const N = piles.length; // кеш решений const cache: Map<string, number> = new Map(); const iter = (coins: number[], k: number): number => { if (k == 0) return 0; // получим ключ и попробуем найти решение в кеше const stateKey = JSON.stringify(coins) let res = cache.get(stateKey) if (res !== undefined) return res; let best = 0 for (let i = 0; i < piles.length; i ++) { if (piles[i].length > coins[i]) { const nextCoins = [...coins] nextCoins[i] ++ const nextRes = piles[i][coins[i]] + iter(nextCoins, k - 1) if (nextRes > best) best = nextRes; } } // запишем решение в кеш cache.set(stateKey, best) return best; } return iter(new Array(N).fill(0), k); } |
Это ускоряет работу программы, но явно не помогает решить задачу при тех граничных условиях, которые заданы. А нас может быть до 1000 куч, и до 2000 операций. Т.е. в кеш будут попадать их разнообразные комбинации — и это что то вроде факториала куч и операций.
Тоже рекурсия, но другой подход (динамическое программирование)
Взглянем немного по-другому на задачу и рекурсию с ней связанную.
Нам нужно распределить общее число операций между кучами монет. Мы можем вообще не брать монеты из какой то кучи. А максимум операций с одной кучей ограничен числом оставшихся операций и числом монет в этой куче.
Что если мы будем брать какое то кол-во монет из одной кучи, а затем вычеркивать её из рассмотрения? Так у нас получается шаг рекурсии — взяли какое кол-во монет N, и на следующей итерации у нас на одну кучу меньше и надо выполнить K — N операций.
Что это нам даёт?
Прежде всего для следующего шага уже не требуется передавать вектор состояния. Мы можем вычеркивать крайнюю кучу, а оставшиеся кучи задаются как номер последней доступной к рассмотрению стопки монет.
Во-вторых, кеш потребует меньше памяти, т.к. состояние описывается двумя числами — номер последней кучи и кол-во оставшихся операций. Это двумерный массив — [число куч x кол-вл операций].
|
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 |
function maxValueOfCoins(piles: number[][], k: number): number { const N = piles.length; // кеш рекурсии const cache: number[][] = new Array(N) const iter = (lastPile: number, coinsLeft: number): number => { // закончились кучи или операции if (coinsLeft == 0 || lastPile < 0) return 0; // используем кеш if (cache[lastPile][coinsLeft] !== -1) return cache[lastPile][coinsLeft] // т.к. мы можно вообще не брать монеты из данной кучи, // то возьмем это как отправную точку let bestRes = iter(lastPile - 1, coinsLeft) // сколько мы можем взять монет из данной кучи const maxCounsToTake = Math.min(coinsLeft, piles[lastPile].length) let coinsAmount = 0 for (let i = 1; i <= maxCounsToTake; i ++) { // берем монету из кучи coinsAmount += piles[lastPile][i - 1] // получаем следующий шаг рекурсии const nextRes = coinsAmount + iter(lastPile - 1, coinsLeft - i) if (nextRes > bestRes) bestRes = nextRes; } // кешируем результат cache[lastPile][coinsLeft] = bestRes return bestRes; } // инициализация кеша, заполним массив -1, чтобы // задать состояние, когда кеш еще не готов. for (let i = 0; i < N; i ++) cache[i] = new Array(k + 1).fill(-1); // запускаем рекурсию return iter(N - 1, k); }; |