صرف العملات والبرمجة الديناميكية

طريقان إلى نفس الفكرة

قبل أن تبدأ

الفكرة الجوهرية

1الجشع ومتى يفشل

بقطع 1 و3 و4 ومبلغ 6: الجشع يأخذ 4 ثم 1 ثم 1 = ثلاث قطع، والأفضل 3+3 = قطعتان.

def greedy(coins, amount):
    used = []
    for c in sorted(coins, reverse=True):
        while amount >= c:
            amount -= c
            used.append(c)
    return used if amount == 0 else None

print(greedy([1, 3, 4], 6))
print(greedy([1, 5, 10, 25], 30))

2جدول عدد الطرق

هذا الشكل الأقرب من المسألة: بكم طريقة تكوّن المبلغ؟ ways[a] يجمع الطرق التي تنتهي بكل قطعة. الحلقة الخارجية على القطع تمنع عدّ نفس المجموعة بترتيب آخر.

def count_ways(coins, amount):
    ways = [1] + [0] * amount
    for c in coins:
        for a in range(c, amount + 1):
            ways[a] += ways[a - c]
    return ways[amount]

print(count_ways([1, 2, 5], 5))
print(count_ways([2], 3))
print(count_ways([1, 5, 10, 25], 100))

3تمرين: أقل عدد قطع

الآن طبّق نفس الفكرة على السؤال الآخر. ابدأ بـ dp = [0] + [inf] * amount، ولكل مبلغ جرّب كل قطعة وخذ min. لو بقي dp[amount] لا نهاية فالمبلغ مستحيل. اختبر على: قطع [1, 3, 4] ومبلغ 6 (الجواب 2)، وقطع [2] ومبلغ 3 (مستحيل)، ومبلغ 0 (الجواب 0).

مثال محلول

المسألة: بكم طريقة تكوّن 4 بقطع 1 و2؟ الجدول: بعد قطعة 1: [1,1,1,1,1]. بعد قطعة 2: ways[2] = 1 + ways[0] = 2، ways[3] = 1 + ways[1] = 2، ways[4] = 1 + ways[2] = 3. الجواب: 3 طرق: 1+1+1+1، 1+1+2، 2+2.

خرافة مقابل حقيقة

أين تقابله في العمل

اختبر فهمك

بطاقات مراجعة سريعة

تحقق من فهمك