الفكرة
في كل خطوة اختر الأفضل محليًّا على أمل الوصول للحلّ الأمثل عالميًّا — دون تراجع.
مثال: صرف الفكّة
أعطِ المبلغ بأقلّ عدد عملات بأخذ أكبر فئة ممكنة أوّلًا:
def change(amount, coins=[100, 50, 25, 10, 5, 1]):
result = []
for coin in coins:
while amount >= coin:
amount -= coin
result.append(coin)
return result
أمثلة شهيرة
- Dijkstra لأقصر مسار.
- Huffman للضغط.
- جدولة الأنشطة (activity selection).
متى تنجح؟
تنجح فقط إذا كان "الاختيار الجشع" يقود فعلًا للحلّ الأمثل (خاصّية الاختيار الجشع). أحيانًا تفشل وتحتاج البرمجة الديناميكية بدلًا منها.
Greedy مقابل DP
- Greedy: قرار واحد لا رجعة فيه لكل خطوة (أسرع).
- DP: يستكشف كل الخيارات ويحفظها (أشمل، أبطأ).
🎯 التالي: التراجع (Backtracking).