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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Декодировка строки

Апрель 30, 2023 г.

Задача 394 с литкода. Дана строка, где присутствуют группы вроде N[string], нужно раскрыть скобки, повторяя строку внутри скобок N раз. Структуры могут быть вложенными. Чтобы выработать решение, рассмотрим пример: [crayon-650dbe8e6cf3b006871752/] ...

Читать

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

Январь 24, 2023 г.

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

Читать

 

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

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



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