Как выбрать наименьшее число монет для сдачи?

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

У вас есть набор номиналов монет: например, 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] — корректно