Як вибрати найменшу кількість монет для здавання?

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

У вас є набір номіналів монет: наприклад, 1, 3, 4, 5. Потрібно видати суму n з мінімальною кількістю монет. Рішення повинно повернути список монет, якими можна отримати суму з мінімальною кількістю елементів.

Жадібний підхід: інтуїтивний, але не завжди правильний

Ідея жадібного алгоритму проста: завжди обирати найбільшу монету, яка менша або дорівнює залишковій сумі. Припустимо, у нас є номінали монет [1, 3, 4] і потрібно видати суму 6.

Жадібний алгоритм візьме спочатку 4, потім 1, потім 1 — разом 3 монети. Але правильна відповідь — [3, 3], всього 2 монети.

Це приклад, коли жадібний підхід дає не оптимальне рішення.

Приклад реалізації жадібного алгоритму

def greedy_coins(coins, amount):
	coins.sort(reverse=True)
	result = []
	for coin in coins:
		while amount >= coin:
			amount -= coin
			result.append(coin)
	return result

# Приклад використання
print(greedy_coins([1, 3, 4], 6)) # Поверне [4, 1, 1], що НЕ оптимально

Оптимальний алгоритм: динамічне програмування

Щоб гарантовано знайти мінімальну кількість монет, використовуємо динамічне програмування. Суть: для кожної суми від 1 до n визначаємо мінімальну кількість монет, необхідну для її отримання.

def min_coins(coins, amount):
	dp = [float('inf')] * (amount + 1)
	dp[0] = 0
	for i in range(1, amount + 1):
		for coin in coins:
			if i - coin >= 0:
				dp[i] = min(dp[i], dp[i - coin] + 1)
	return dp[amount] if dp[amount] != float('inf') else -1

# Приклад
print(min_coins([1, 3, 4], 6)) # Поверне 2 — оптимальна кількість монет

Якщо потрібно відновити самі монети, використовуємо додатковий масив:

def get_coin_list(coins, amount):
	dp = [float('inf')] * (amount + 1)
	prev = [-1] * (amount + 1)
	dp[0] = 0
	for i in range(1, amount + 1):
		for coin in coins:
			if i - coin >= 0 and dp[i - coin] + 1 < dp[i]:
				dp[i] = dp[i - coin] + 1
				prev[i] = coin
	if dp[amount] == float('inf'):
		return []

	result = []
	while amount > 0:
		result.append(prev[amount])
		amount -= prev[amount]
	return result

# Приклад
print(get_coin_list([1, 3, 4], 6)) # Поверне [3, 3]

Коли жадібний алгоритм працює?

Жадібний алгоритм працює ідеально, якщо номінали монет є канонічною системою — тобто кожен наступний номінал кратний попередньому (наприклад, [1, 2, 5, 10, 20, 50]).

У випадку нестандартних номіналів (особливо коли між номіналами немає чіткої кратності), жадібний алгоритм часто помиляється.

Приклад: коли жадібний підхід правильний

print(greedy_coins([1, 2, 5, 10], 18)) # Поверне [10, 5, 2, 1] — коректно