Aclıqlı alqoritm həlli addım-addım qurur: hər addımda ən yaxşı görünən variantı seçir və onu bir daha dəyişmir. Axtarış və geri qayıtma yoxdur, ona görə vaxt adətən O(n log n) (çeşidləmə) və ya O(n) olur. Əvəzində alqoritm yalnız bəzi məsələlərdə düzgündür.
Aclıqlıq nə vaxt işləyir
- Aclıqlı seçim xassəsi: ən yaxşı lokal seçimi optimal həllin bir hissəsi etmək olar.
- Optimal alt struktur: seçimdən sonra qalan məsələnin optimumu bütün məsələnin optimumuna daxildir.
Sikkələrin dəyişdirilməsi
from itertools import combinations_with_replacement
def greedy_coins(coins, amount):
result = []
for coin in sorted(coins, reverse=True):
while amount >= coin:
amount -= coin
result.append(coin)
return result
def optimal_coins(coins, amount):
for k in range(1, amount + 1):
for combo in combinations_with_replacement(coins, k):
if sum(combo) == amount:
return list(combo)
print(greedy_coins([1, 5, 10, 25], 63))
print(greedy_coins([1, 3, 4], 6), optimal_coins([1, 3, 4], 6))