Greedy Algorithm কী?
গ্রিডি অ্যালগরিদম প্রতিটি ধাপে সেই মুহূর্তে সবচেয়ে ভালো (locally optimal) বিকল্প বেছে নেয়, এই আশায় যে এটি সামগ্রিকভাবেও সেরা (globally optimal) হবে।
বাস্তব উদাহরণ: টাকা ভাঙানো
ধরুন আপনাকে ৩৮ টাকা ফেরত দিতে হবে (নোট: ২০, ১০, ৫, ২, ১):
৩৮ টাকা ভাঙানো: → ২০ টাকা (বাকি ১৮) → ১০ টাকা (বাকি ৮) → ৫ টাকা (বাকি ৩) → ২ টাকা (বাকি ১) → ১ টাকা (বাকি ০) মোট ৫টি নোট
Python উদাহরণ
def min_coins(amount, coins):
coins.sort(reverse=True)
result = []
for coin in coins:
while amount >= coin:
result.append(coin)
amount -= coin
return result
print(min_coins(38, [20,10,5,2,1]))
# [20, 10, 5, 2, 1]
সুবিধা ও অসুবিধা
- ✅ দ্রুত ও সহজ
- ❌ সবসময় সর্বোত্তম সমাধান দেয় না