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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

87. Scramble string - задача о перетасованных строках

Март 30, 2023 г.

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

Читать

Игра в камни

Май 27, 2023 г.

Серия задач StoneGame на leetcode - образец игры, где требуется просчитать оптимальную стратегию. Выигрыш/проигрыш начинающего партию предопределен, и второй участник лишь может надеяться на ошибку первого. Но это не наш случай, т.к. по условию ...

Читать

Классическая задача о размене монет

Январь 24, 2023 г.

Дана сумма amount и номиналы монет. Требуется разменять сумму минимальным набором монет. Если рассматривать набор монет, который используется в реальной жизни, т.е. [1коп, 5коп, 10коп, 50коп, 1р, 2р, 5р, 10р], то во-первых, решение всегда существует, ...

Читать

Вычисление заголовка столбца в Excel

Март 23, 2023 г.

Leetcode задача #168. Excel Sheet column title.Задача помечена как простая, тем не менее, не сразу понял как её решать. Дано число, это номер столбца для Excel таблицы, требуется сгенерировать его буквенное имя. Иными словами сопоставить 1 -> A, ...

Читать
 

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

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



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