فحص إمكانية جمع محتويات مصفوفة C++ إلى قيمة معينة

في بعض الأحيان، يكون من الضروري في لغة البرمجة C++ فحص ما إذا كانت محتويات مصفوفة يمكن أن تجمع إلى قيمة معينة. في سياق السؤال الخاص بك، تريد التحقق مما إذا كان بإمكانك العثور على مجموعة فرعية من القيم في المصفوفة يمكن أن تضيف إلى 20. لنقم بمناقشة ذلك بشكل مفصل.

أولاً وقبل كل شيء، دعونا نعتمد على أنك قد تملك مصفوفة تحتوي على أرقام، وتحديداً:

cppCopy code
int myArray[] = {2, 5, 8, 3, 2, 1, 9};

الهدف هو العثور على مجموعة فرعية من هذه القيم تضيف إلى 20. لحل هذه المشكلة، يمكن استخدام مفهوم البحث عن مجموعة فرعية (Subset Sum)، حيث يمكننا استخدام خوارزمية ديناميكية للتحقق من إمكانية الوصول إلى مجموعة معينة.

سنقوم بإنشاء دالة تقوم بتنفيذ هذا البحث. دعونا نلقي نظرة على تقديم مثال لهذا الحال:

cppCopy code
#include 
#include 

bool canAddUpToSum(const std::vector<int>& arr, int targetSum) {
    int n = arr.size();
    std::vectorbool>> dp(n + 1, std::vector<bool>(targetSum + 1, false));

    for (int i = 0; i <= n; ++i)
        dp[i][0] = true;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= targetSum; ++j) {
            if (j < arr[i - 1]) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - arr[i - 1]];
            }
        }
    }

    return dp[n][targetSum];
}

int main() {
    std::vector<int> myArray = {2, 5, 8, 3, 2, 1, 9};
    int targetSum = 20;

    if (canAddUpToSum(myArray, targetSum)) {
        std::cout << "Yes, there is a subset that adds up to " << targetSum << ".\n";
    } else {
        std::cout << "No, there is no subset that adds up to " << targetSum << ".\n";
    }

    return 0;
}

تستخدم هذه الدالة مصفوفة ثنائية الأبعاد لتخزين نتائج البحث. إذا كان بإمكان الوصول إلى مجموعة معينة تضيف إلى القيمة المستهدفة، ستعود الدالة بقيمة صحيحة، وإلا ستعود بقيمة خاطئة.

نأمل أن تكون هذه الإرشادات مفيدة لك، وأن تمكنك من تحقيق هدفك في فحص إمكانية جمع محتويات المصفوفة إلى قيمة محددة.

بالطبع، دعنا نوسع قليلاً في الموضوع. الحل الذي تم توفيره يستند إلى مفهوم البرمجة الديناميكية، الذي يعتبر فعالًا في معالجة مشاكل البحث عن مجموعة فرعية. دعونا نقم بتفكيك الحلاقرب إلى المفهوم والتفاصيل الدقيقة.

أساسيات الحلا:

1. المصفوفة الثنائية:

   • نستخدم مصفوفة ثنائية الأبعاد (dp) لتخزين النتائج. dp[i][j] تمثل ما إذا كان بإمكاننا الوصول إلى مجموعة من العناصر الأولى i تضيف إلى j.

2. التعبير التكراري:

   • نستخدم تكرارًا ديناميكيًا لملء المصفوفة. في كل خطوة، نتحقق مما إذا كان بإمكاننا الوصول إلى القيمة الحالية j باستخدام أو عدم استخدام العنصر الحالي arr[i-1].

3. القيمة المستهدفة:

   • نقوم بفحص القيمة المستهدفة (targetSum) في النهاية، حيث تكون dp[n][targetSum] هي الإجابة النهائية.

في الكود المقدم، يتم إجراء هذا البحث بطريقة فعالة، ويمكن تعديل الكود لتناسب حالات استخدام أخرى. عند تشغيل البرنامج، يتم إظهار رسالة تشير إما إلى وجود مجموعة فرعية تضيف إلى القيمة المستهدفة أو عدم وجودها.

يُشير الكود أيضًا إلى استخدام مكتبة لتخزين المصفوفة، والتي تسهل عمليات التحكم في الحجم وتوفير أكواد أكثر قراءةً وفهمًا.

إذا كان لديك أي أسئلة إضافية أو إذا كنت بحاجة إلى توضيح إضافي حول أي جزء من الكود، فلا تتردد في طرحها.