مسألة صرف العملات
الدرس 8 من 15 في دورة البرمجة الديناميكية 101 على Coddy.
تعد مشكلة تبديل العملات (coin change problem) مشكلة كلاسيكية في البرمجة الديناميكية. بمعطيات مجموعة من العملات ذات فئات مختلفة ومبلغ إجمالي من المال، فإن المهمة هي العثور على أقل عدد من العملات اللازمة لتكوين المبلغ المطلوب.
على سبيل المثال، لنفترض أن لدينا عملات بفئات [1، 5، 10] ونريد تكوين المبلغ 15. سيكون الحد الأدنى لعدد العملات المطلوبة هو 2 (عملة من فئة 10 وعملة من فئة 5).
لحل هذه المشكلة باستخدام البرمجة الديناميكية، يمكننا إنشاء جدول بصفوف تمثل فئات العملات وأعمدة تمثل المبالغ من 0 إلى المبلغ الإجمالي المعطى. ثم نقوم بملء الجدول بطريقة تصاعدية (bottom-up) من خلال حساب الحد الأدنى لعدد العملات اللازمة لتكوين كل مبلغ باستخدام عملات كل فئة.
التحدي
متوسطاكتب برنامجًا يأخذ مدخلين: قائمة بفئات العملات المعدنية ومبلغًا مستهدفًا، ويعيد الحد الأدنى لعدد العملات المعدنية اللازمة لتكوين المبلغ المستهدف.
على سبيل المثال، بالنسبة للفئات [1, 5, 10] والمبلغ المستهدف 15، يجب أن يكون الناتج 2.
جرّب بنفسك
def min_coins(coins, target):
# اكتب الكود هنا