Як вирішується класична задача розміну монет за допомогою жадібного алгоритму?

АлгоритмиJunior~2 хв читання

Коротка відповідь

Жадібний алгоритм розміну монет: на кожному кроці бери найбільший номінал, який не перевищує поточний залишок суми, віднімай його і повторюй, доки залишок не стане нулем. Він оптимальний для «канонічних» наборів номіналів (наприклад, 1, 5, 10, 25), але може дати неоптимальний результат для довільних наборів. Швидка реалізація використовує цілочисельне ділення і працює за O(k), де k - кількість номіналів.

Детальна відповідь

Ідея жадібного алгоритму

Ми хочемо розміняти суму S мінімальною кількістю монет із набору номіналів C. Жадібний підхід щоразу обирає монету з максимально можливим номіналом, який не перевищує поточний залишок. Це природна евристика, яка виявляється оптимальною не завжди, але часто - для спеціальних («канонічних») систем номіналів, до яких належать реальні валюти.

Покроковий алгоритм

Відсортуйте номінали за спаданням.
Для кожного номіналу c з відсортованого списку візьміть максимально можливу кількість монет цього номіналу: count = ⌊S / c⌋.
Зменшіть залишок: S = S - count × c. Перейдіть до наступного номіналу.
Повторюйте, доки S не стане 0. Якщо S > 0 після обробки всіх номіналів, розмін неможливий із заданим набором.

Приклад (канонічна валюта)

Номінали: {1, 5, 10, 25}. Сума: 63.

Жадібний вибір: 25 -> 25 -> 10 -> 1 -> 1 -> 1. Разом 6 монет. Це оптимально.

javascript

function greedyChange(coins, amount) {
  // Захист від сміттєвих вхідних даних
  if (!Array.isArray(coins) || coins.length === 0) throw new Error('coins must be a non-empty array');
  if (!Number.isInteger(amount) || amount < 0) throw new Error('amount must be a non-negative integer');

  // Сортування за спаданням
  const sorted = [...coins].sort((a, b) => b - a);

  const result = [];
  let remaining = amount;

  for (const c of sorted) {
    if (c <= 0 || !Number.isInteger(c)) throw new Error('coin denominations must be positive integers');
    const count = Math.floor(remaining / c);
    if (count > 0) {
      result.push({ coin: c, count });
      remaining -= count * c;
    }
  }

  if (remaining !== 0) {
    // Розмін неможливий (наприклад, немає монети 1)
    return { ok: false, used: result, remaining };
  }

  const totalCoins = result.reduce((s, x) => s + x.count, 0);
  return { ok: true, used: result, totalCoins };
}

// Приклад: канонічна система {1,5,10,25}
console.log(greedyChange([1,5,10,25], 63));
// => { ok: true, used: [ {coin:25,count:2}, {coin:10,count:1}, {coin:1,count:3} ], totalCoins: 6 }

Контрприклад (де жадібний не оптимальний)

Номінали {1, 3, 4}, сума 6: жадібний дасть 4 + 1 + 1 = 3 монети, оптимально 3 + 3 = 2 монети.
Номінали {1, 5, 7}, сума 10: жадібний дасть 7 + 1 + 1 + 1 = 4 монети, оптимально 5 + 5 = 2 монети.

Коректність і коли жадібний працює

Оптимальність на «канонічних» наборах номіналів: реальні валюти (наприклад, {1, 5, 10, 25, 50}) сконструйовані так, щоб жадібний алгоритм завжди був оптимальним.
Достатні (але не обов'язкові) умови: c1 = 1, і кожен наступний номінал кратний попередньому (наприклад, {1, 2, 4, 8, ...}); або система «супервозрастаюча», де кожен наступний номінал строго більший за суму всіх менших. У таких випадках обмінним аргументом доводиться оптимальність жадібного вибору.
Для довільних наборів гарантій немає, і жадібний може програвати динамічному програмуванню.

Складність

Якщо використовувати цілочисельне ділення (як у коді), ми робимо по одній дії на номінал, тобто O(k), де k - кількість номіналів (плюс O(k log k) на сортування, якщо номінали не відсортовані заздалегідь). Якщо ж віднімати монети по одній, складність буде O(M), де M - загальна кількість виданих монет.

Реалізація (JavaScript)

javascript

// Жадібний розмін: завжди обираємо найбільшу підходящу монету
function greedyChange(coins, amount) {
  if (!Array.isArray(coins) || coins.length === 0) throw new Error('coins must be a non-empty array');
  if (!Number.isInteger(amount) || amount < 0) throw new Error('amount must be a non-negative integer');

  const sorted = [...new Set(coins)].sort((a, b) => b - a); // унікалізуємо і сортуємо
  if (sorted.some(c => !Number.isInteger(c) || c <= 0)) throw new Error('all coin denominations must be positive integers');

  const used = [];
  let remaining = amount;

  for (const c of sorted) {
    const cnt = Math.floor(remaining / c);
    if (cnt > 0) {
      used.push({ coin: c, count: cnt });
      remaining -= cnt * c;
    }
  }

  return {
    ok: remaining === 0,
    used,
    remaining,
    totalCoins: used.reduce((s, x) => s + x.count, 0)
  };
}

// Приклади
console.log('63 за {1,5,10,25}:', greedyChange([1,5,10,25], 63));
console.log('6 за {1,3,4}:', greedyChange([1,3,4], 6)); // жадібний дає 3 монети, неоптимально
console.log('10 за {1,5,7}:', greedyChange([1,5,7], 10)); // жадібний дає 4 монети, неоптимально

Коли потрібен динамічний підхід

Якщо набір номіналів не канонічний або потрібна гарантовано мінімальна кількість монет для будь-яких вхідних даних, використовуйте динамічне програмування (наприклад, класичний алгоритм із таблицею dp за сумою). Він дає оптимум за O(k·S) за часом і O(S) за пам'яттю.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.