49. مثال على الخوارزمية الجشعة: مشكلة صرف العملات (الحالة البسيطة)

تطرح مشكلة صرف العملات السؤال التالي: بالنظر إلى مجموعة من فئات العملات، ما هو الحد الأدنى لعدد العملات المطلوبة لصنع مبلغ معين؟

نظام العملات الأمريكي (حيث ينجح الجشع)

في العملة الأمريكية القياسية (1، 5، 10، 25 سنتاً)، يضمن النهج الجشع (اختيار أكبر فئة ممكنة دائماً) الحد الأدنى لعدد العملات.

الهدف: 41 سنتاً

1. أخذ أكبر عملة <= 41: 25. المتبقي: 16.
2. أخذ أكبر عملة <= 16: 10. المتبقي: 6.
3. أخذ أكبر عملة <= 6: 5. المتبقي: 1.
4. أخذ أكبر عملة <= 1: 1. المتبقي: 0.

إجمالي العملات: 4. وهذا هو الحل الأمثل.

الخوارزمية

python coins = [25, 10, 5, 1] # Assumes sorted descending def greedy_change(amount, coins): count = 0 for coin in coins: while amount >= coin: amount -= coin count += 1 return count