Рассмотрим задачу:

Есть неограниченное количество монет разного номинала.

Необходимо вернуть сдачу минимальным количеством этих монет.

Предположим, что у нас есть монеты достоинством 1, 2, 5 и 10 рублей и нам нужно вернуть 5 рублей сдачи. Мы можем это сделать несколькими способами:

  • 1 + 1 + 1 + 1 + 1
  • 1 + 1 + 1 + 2
  • 1 + 2 + 2
  • 5

Таким образом, минимальное количество монет для сдачи равно 1. Нам достаточно отдать пятирублевую монету.

Известно, что:

  1. Если нам нужно вернуть сдачу размером change, то использовать монеты больше чем change мы не можем (в примере это монета достоинством 10 рублей).
  2. Если мы использовали монету достоинством coin (coin <= change), то нам останется вернуть change-coin рублей.
  3. Решение задачи будет равным минимальному количеству монет, которое нужно для возврата change-coin рублей + 1 монета, которую вернули в пункте 2.

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

Определим рекурсивную формулу, по которой будем производить вычисления:

\[M(k) = min_i\{M(k-i)\} + 1,\]

где k - cумма для сдачи, i - номинал монеты. Для нашего случая i = 1, 2, 5, 10.

Реализация решения по этой формуле выглядит так (Java):

public static int makeChange(int change) {
  if (change < 0)
    return Integer.MAX_VALUE;

  if (change == 1 || change == 2 || change == 5 || change == 10) {
    return 1;
  }

  int min1 = makeChange(change - 1);
  int min2 = makeChange(change - 2);
  int min5 = makeChange(change - 5);
  int min10 = makeChange(change - 10);

  return minimum(min1, min2, min5, min10) + 1;
}

Начальные условия - сдача, которую нужно вернуть.

Условие остановки рекурсии - оставшуюся сумму можно сразу вернуть одной монетой или для возврата оставшейся суммы обрабатываемый номинал слишком велик.

Этот алгоритм имеет сложность \(O(2^n)\) и на моём компьютере уже при попытке вернуть сдачу в 40 рублей ищет решение очень долго.

Оптимизировать решение можно с помощью динамического программирования с запоминанием (memoization).

public static int makeChange2(int change) {
  if (change == 1 || change == 3 || change == 5 || change == 10) {
    return 1;
  }

  int memo[] = new int[change + 1];
  int max = Integer.MAX_VALUE;
  Arrays.fill(memo, max);

  if (change > 1)
    memo[1] = 1;
  if (change > 3)
    memo[3] = 1;
  if (change > 5)
    memo[5] = 1;
  if (change > 10)
    memo[10] = 1;

  for (int i = 2; i <= change; i++) {
    if (i == 1 || i == 3 || i == 5 || i == 10) {
      continue;
    }
    int min1 = (i > 1) ? memo[i - 1] : max;
    int min3 = (i > 3) ? memo[i - 3] : max;
    int min5 = (i > 5) ? memo[i - 5] : max;
    int min10 = (i > 10) ? memo[i - 10] : max;

    memo[i] = minimum(min1, min3, min5, min10) + 1;
  }

  System.out.println(Arrays.toString(memo));
  return memo[change];

}

В этом варианте решения сложность по времени будет \(O(n)\), но требуется дополнительная память на \(n\) сумм сдачи.

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