Решение проблемы с банкоматом с помощью динамического программирования

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

В предыдущей статье мы решили эту проблему с помощью жадный алгоритм. Однако такой подход не всегда гарантирует оптимальное решение.

В этой статье мы решим задачу с помощью динамического программирования.

Постановка задачи

Для банкомата, содержащего N банкнот разного достоинства, напишите функцию, которая будет снимать указанную сумму денег, используя минимально возможное количество банкнот. Функция должна возвращать массив чисел или null, если сумма не может быть снята.

Динамическое программирование

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

Классический пример — последовательность Фибоначчи. Перед вычислением F(N) мы вычисляем F(N-1) и так далее, пока не достигнем подзадачи F(0) , для которого ответ равен 1.

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

Пример

Допустим, у нас в банкомате есть следующие купюры: [1000, 500, 100], и мы хотим снять 1100. Мы можем создать таблицу для хранения значений F(N), где N — количество банкнот:

F(0)

Мы можем получить только сумму 0, используя 0 банкнот:

| Сумма | Банкноты | |----|----| | 0 | [] |

F(1)

Складываем банкноту 1000 и получаем 2 возможные комбинации:

| Сумма | Банкноты | |----|----| | 0 | [] | | 1000 | [1000] |

F(2)

Добавляем в предыдущую таблицу еще одну банкноту 500 и получаем 2 новые комбинации:

| Сумма | Банкноты | |----|----| | 0 | [] | | 1000 | [1000] | | 500 | [500] | | 1500 | [1000, 500] |

F(3)

Добавляем в предыдущую таблицу еще одну банкноту 100 и получаем 4 новые комбинации:

| Сумма | Банкноты | |----|----| | 0 | [] | | 1000 | [1000] | | 500 | [500] | | 1500 | [1000, 500] | | 100 | [100] | | 1100 | [1000, 100] | | 600 | [500, 100] | | 1600 | [1000, 500, 100] |

Результат

Ищем в таблице ключ 1100 и получаем ответ [1000, 100].

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

Алгоритм

1. Создайте таблицу для хранения суммы и банкнот

2. Повторите от 1 до N, где N — количество банкнот, и для каждого n сделайте следующее:

3. Создайте временную таблицу.

4. Скопируйте каждую строку из основной таблицы, добавьте в нее текущую банкноту и сохраните ее во временной таблице.
5. Скопируйте значения из временной таблицы в основную таблицу.
6. Если в основной таблице уже есть строка с такой же суммой, отдайте приоритет значению из временной таблицы.
7. Найдите в таблице строку с нужной суммой и выведите ответ. Если такой строки в таблице нет, то решение для этих значений недоступно.

Код

const withdraw = (total, _coins) => {
  coins = [..._coins].sort((a, b) => b - a);

  // Main table
  // key - sum
  // value - array of banknotes
  let sums = {0: []};

  // Iterator from 1 to N banknotes
  for (key in coins) {
    const val = coins[key]; // Banknote value
    const newSums = {}; // Temporary table

    // Iterator over elements of the main table
    for ([key, values] of Object.entries(sums)) {
      const newKey = parseInt(key) + val; // New sum
      newSums[newKey] = [...values, val]; // New set of banknotes
    }

    sums = {
      ...newSums,
      ...sums, // priority to the main table
    };
  }

  return sums[total] || null;
};

Сложность алгоритма

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

Следовательно, временная сложность алгоритма составляет O(NS), где N — количество банкнот, а S — сумма снятия.

Обзор

Мы научились использовать динамическое программирование для решения этой проблемы. В отличие от жадных алгоритмов динамическое программирование может гарантировать оптимальное решение проблемы ATM во всех случаях. Временная сложность динамического программирования составляет O(NS), где N — количество банкнот, а S — сумма снятия. Хотя эта сложность относительно высока, это все же лучше, чем создание всех возможных комбинаций.