حل مشكلة تغيير العملة (Coin Change Problem) باستخدام البرمجة الديناميكية مع أمثلة في Python، Java، و C

1. مقدمة عن المشكلة

وصف المشكلة:
مشكلة تغيير العملة (Coin Change Problem) هي مشكلة كلاسيكية في البرمجة الديناميكية. الهدف هو إيجاد عدد الطرق المختلفة لإعطاء المبلغ المطلوب باستخدام عملات ذات فئات محددة، أو إيجاد أقل عدد من العملات التي تحتاجها لتحقيق هذا المبلغ.

حالة استخدام:
تستخدم هذه المشكلة في تطبيقات مثل إيجاد أقل عدد من الأوراق المالية أو العملات النقدية لإعطاء الباقي في ماكينة الصراف الآلي أو في آلات البيع.

المدخلات والمخرجات:

• المدخلات: قائمة بفئات العملات المتاحة ومبلغ الهدف.
• المخرجات: أقل عدد من العملات المطلوبة لتحقيق مبلغ الهدف، أو عدد الطرق الممكنة لتغيير المبلغ.

2. شرح تعليمي للحل

مفهوم مشكلة تغيير العملة:

هناك طريقتان شائعتان لحل مشكلة تغيير العملة:

• الحل باستخدام البرمجة الديناميكية (لعدد الطرق الممكنة): نستخدم جدول ثنائي الأبعاد لتتبع عدد الطرق الممكنة لإعطاء مبلغ معين باستخدام عملات محددة.
• الحل باستخدام البرمجة الديناميكية (لأقل عدد من العملات): نستخدم جدول لتتبع أقل عدد من العملات المطلوبة لكل مبلغ ممكن حتى مبلغ الهدف.

تعقيد الوقت:

• O(m * n)، حيث m هو المبلغ و n هو عدد فئات العملات.

تعقيد المساحة:

• O(m) لاستخدام المصفوفة المساعدة.

3. الحل في Python

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    # بناء جدول البرمجة الديناميكية
    for coin in coins:
        for x in range(coin, amount + 1):
            dp[x] = min(dp[x], dp[x - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

# استخدام المثال
coins = [1, 2, 5]
amount = 11
print("أقل عدد من العملات المطلوبة هو:", coin_change(coins, amount))

4. الحل في Java

import java.util.Arrays;

public class CoinChange {

    // دالة لإيجاد أقل عدد من العملات
    public static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        // بناء جدول البرمجة الديناميكية
        for (int coin : coins) {
            for (int x = coin; x <= amount; x++) {
                dp[x] = Math.min(dp[x], dp[x - coin] + 1);
            }
        }

        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 11;
        System.out.println("أقل عدد من العملات المطلوبة هو: " + coinChange(coins, amount));
    }
}

5. الحل في C

#include <stdio.h>
#include <limits.h>

int coinChange(int coins[], int n, int amount) {
    int dp[amount + 1];
    for (int i = 0; i <= amount; i++)
        dp[i] = amount + 1;
    dp[0] = 0;

    // بناء جدول البرمجة الديناميكية
    for (int i = 0; i < n; i++) {
        for (int x = coins[i]; x <= amount; x++) {
            if (dp[x - coins[i]] != amount + 1) {
                dp[x] = dp[x] < dp[x - coins[i]] + 1 ? dp[x] : dp[x - coins[i]] + 1;
            }
        }
    }

    return dp[amount] > amount ? -1 : dp[amount];
}

int main() {
    int coins[] = {1, 2, 5};
    int amount = 11;
    int n = sizeof(coins) / sizeof(coins[0]);
    int result = coinChange(coins, n, amount);
    printf("أقل عدد من العملات المطلوبة هو: %d\n", result);
    return 0;
}