Задача о наибольшей сумме монет

Решаем задачу № 2218 с leetcode — Maximum Value of K Coins From Piles.

В названии фигурирует слова монеты и стопки. Если представить себе, что монеты могут быть произвольного номинала, то да — суть именно такая. У нас есть стопки монет, и дано число операций, за каждую из которых, мы можем взять монету из произвольной кучи.

Нужно вернуть максимальную сумму, которую возможно набрать при таких условиях.

Решение «в лоб»

Первый заход попробуем реализовать грубой силой. Представьте себе следующую рекурсию:

  1. Выбираем любую стопку и берем от туда «монету».
  2. Перебираем все стопки монет.
  3. Результат шага — это лучшая сумма = взятая монета + очередной шаг рекурсии. Где мы должны решить задачу для K — 1 операций, зная о числе оставшихся монет в кучах.
  4. Если число операции на очередном шаге равно нулю мы возвращаем ноль, т.к. больше монет мы брать не можем.

Основная проблема — в затратах на описание очередного шага рекурсии. Число оставшихся монет — это массив, который указывает сколько монет было взято в каждой куче.

Этот цикл длится буквально бесконечность для совсем не больших наборов монет и числа операций. Чтобы как то улучшить ситуацию, мы можем кешировать рекурсию. Состояние целиком описывается вектором coins — числом взятых монет из определенных куч.

Сериализуем массив, чтобы получить одномерный ключ для кеша. Вот, что получилось:

Это ускоряет работу программы, но явно не помогает решить задачу при тех граничных условиях, которые заданы. А нас может быть до 1000 куч, и до 2000 операций. Т.е. в кеш будут попадать их разнообразные комбинации — и это что то вроде факториала куч и операций.

Тоже рекурсия, но другой подход (динамическое программирование)

Взглянем немного по-другому на задачу и рекурсию с ней связанную.

Нам нужно распределить общее число операций между кучами монет. Мы можем вообще не брать монеты из какой то кучи. А максимум операций с одной кучей ограничен числом оставшихся операций и числом монет в этой куче.

Что если мы будем брать какое то кол-во монет из одной кучи, а затем вычеркивать её из рассмотрения? Так у нас получается шаг рекурсии — взяли какое кол-во монет N, и на следующей итерации у нас на одну кучу меньше и надо выполнить K — N операций.

Что это нам даёт?

Прежде всего для следующего шага уже не требуется передавать вектор состояния. Мы можем вычеркивать крайнюю кучу, а оставшиеся кучи задаются как номер последней доступной к рассмотрению стопки монет.

Во-вторых, кеш потребует меньше памяти, т.к. состояние описывается двумя числами — номер последней кучи и кол-во оставшихся операций. Это двумерный массив — [число куч x кол-вл операций].

Написать комментарий

Мало букафф? Читайте есчо !

Задача о подмножествах

Апрель 21, 2023 г.

В теории программирования большой класс задач связан с перебором подмножеств, и на leetcode как раз попалась пара похожих задач, чтобы можно было их разобрать как пример - 78 Subsets и 90 Subsets II. Формулировка следующая - есть набор (множество) ...

Читать

Задача следующей комбинации (next permutation)

Март 13, 2023 г.

Мне понадобилось какое то время, чтобы понять верный подход к решению, делюсь подробным разбором этой задачи. Ставится она так: есть набор (массив) элементов, чаще всего чисел, требуется найти следующей по порядку возрастания набор этих элементов. ...

Читать

 

Комментарии к «Задача о наибольшей сумме монет»

Понравилась статья? Есть вопросы? - пишите в комментариях.



Комментарий: