Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Як вирішується класична задача розміну монет за допомогою жадібного алгоритму?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

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

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

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

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

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

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

1. Відсортуйте номінали за спаданням.
2. Для кожного номіналу c з відсортованого списку візьміть максимально можливу кількість монет цього номіналу: count = ⌊S / c⌋.
3. Зменшіть залишок: S = S - count × c. Перейдіть до наступного номіналу.
4. Повторюйте, доки 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) за пам'яттю.

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати763 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.