Проблема банкомата: почему жадный алгоритм не является оптимальным решением

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

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

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

Возможные решения

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

Жадный алгоритм

Жадный алгоритм – это алгоритм, который принимает локально оптимальные решения на каждом шаге, предполагая, что окончательное общее решение будет оптимальным.

В этом случае жадный алгоритм можно выразить следующим образом:

1. Возьмите максимальную банкноту, меньшую или равную требуемой сумме.
2. Запишите эту банкноту в результат и вычтите ее из общей суммы.
3. Повторяйте шаг 1, пока вся сумма не будет снята.

Пример

Предположим, банкноты в банкомате составляют [5000, 1000, 500, 500, 100], а сумма для снятия составляет 1600.

1. 5000 не подходит, так как это больше требуемой суммы.
2. Подходит 1000 (меньше 1600), остается 600 (1600–1000).
3. Подходит 500 (меньше 600), остается 100 (600–500).
4. Подходит 100 (равно 100), остаток равен 0 (100–100).
5. Остаток равен 0, поэтому результат равен [1000, 500, 100].

Код

const withdraw = (total, _coins) => {
  // Sort the banknotes
  coins = _coins.slice().sort((a, b) => b - a);

  let res = [];
  let balance = total;

  // Iterate through all the banknotes
  for (let i = 0; i < coins.length; i++) {
    // If the banknote is larger than the required sum, skip it.
    if (coins[i] > balance) continue;

    res.push(coins[i]); // Record the banknote in the result.
    balance -= coins[i]; // Update the balance.

    // If the balance is zero, a solution has been found.
    if (balance === 0) {
      return res;
    };
  }

  return null;
};

Проблема с жадным алгоритмом

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

Пример

Предположим, банкноты в банкомате составляют [1000, 800, 500, 100, 100, 100], а сумма для снятия составляет 1300.

1. Подходит 1000 (меньше 1300), остается 300 (1300–1000)
2. 800 не подходит (больше 300)
3. 500 не подходит (больше 300)
4. Подходит 100 (меньше 300), остается 200 (300–100)
5. Подходит 100 (меньше 200), остается 100 (200–100)
6. Подходит 100 (равно 100), остаток равен 0 (100–100)
7. Остаток равен 0, поэтому результат равен [1000, 100, 100, 100].

Результат [1000, 100, 100, 100] не является оптимальным, так как эту сумму можно выпустить двумя банкнотами [800, 500]. На первом шаге мы приняли локально правильное решение, но в целом это решение неоптимально.

Обзор

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

Ведущий образ создан со стабильным распространением.