مجموع المجموعة والتقسيم
بلوغ هدف باستخدام مجموعة جزئية مختارة
مجموع المجموعة والتقسيم درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 4 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
مسألة مجموع المجموعة الجزئية
مع إعطائك أعدادًا وهدفًا، هل يمكن لأي مجموعة جزئية أن يكون مجموعها مساويًا للهدف تمامًا؟ إنها مسألة حقيبة ظهر تكون فيها القيمة مساوية للوزن.
DP منطقية، لا قيمية
تتتبّع هنا إمكانية الوصول، لا القيمة القصوى. لتكن dp[s] مساوية لـ True عندما يكون هناك مجموعة جزئية يساوي مجموعها s تمامًا.
dp = [False] * (target + 1)
dp[0] = Trueالصفر قابل للوصول دائمًا
مجموع المجموعة الجزئية الخالية يساوي صفرًا، لذا تبدأ dp[0] بقيمة True. وتبدأ كل المبالغ الأخرى بقيمة False حتى يثبت أحد الأعداد إمكانية الوصول إليها.
الانتقال
لكل عدد، علّم s بأنه قابل للوصول إذا كانت s - num قابلة للوصول مسبقًا. ويمكن لعدد واحد أن يغيّر حالة مبالغ كثيرة إلى True.
for num in nums:
for s in range(target, num - 1, -1):
dp[s] = dp[s] or dp[s - num]بالعكس مرة أخرى
يُستخدم كل عدد مرة واحدة كحد أقصى، لذا تعمل الحلقة الداخلية بالعكس، تمامًا كما في 0/1 knapsack. أما المرور إلى الأمام فسيعيد استخدام العدد.
اقرأ الحكم
بعد معالجة جميع الأعداد، تجيب dp[target] عن السؤال. وتعني True وجود مجموعة جزئية صالحة، بينما تعني False استحالة ذلك.
ننتقل إلى التقسيم
تسأل مسألة التقسيم: هل يمكنك تقسيم المصفوفة إلى جزأين متساويين في المجموع؟ إنها تختزل مباشرة إلى مسألة مجموع المجموعة الجزئية.
اقسم المجموع إلى نصفين
إذا كان المجموع الكلي فرديًا، فمن المستحيل تكوين نصفين متساويين، لذا أجب بالنفي فورًا. وإلا فالهدف ببساطة هو total // 2.
total = sum(nums)
if total % 2:
return False
target = total // 2أعد استخدام مجموع المجموعة الجزئية
اسأل الآن فقط عما إذا كانت مجموعة جزئية ما تصل إلى total // 2. فإذا بلغ أحد النصفين الهدف، فسيكوّن الباقي النصف الثاني المطابق تلقائيًا.
التعقيد
التكلفة من رتبة n مضروبة في الهدف، وهو حد شبه متعدد الحدود. تكون الخوارزمية سريعة عندما يكون الهدف صغيرًا، وبطيئة عندما تكون المجاميع ضخمة.
عائلة واحدة من المسائل
تشترك مسائل مجموع المجموعة الفرعية والتقسيم وحقيبة 0/1 في محرّك واحد. تعرّف على نمط خذ أو اترك، ثم أعد استخدام الحلقة نفسها.
تحقّق سريع
اختبر اختزال التقسيم.
مراجعة
حللتَ مجموع المجموعة الفرعية باستخدام DP منطقي وحلقة عكسية، ثم اختزلتَ التقسيم إلى الوصول إلى total // 2. المحرّك نفسه، ونتائج جديدة. ✅
الأسئلة الشائعة
هل درس «مجموع المجموعة والتقسيم» مجاني؟
نعم — نص درس «مجموع المجموعة والتقسيم» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «مجموع المجموعة والتقسيم»؟
بلوغ هدف باستخدام مجموعة جزئية مختارة تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 4 من أصل 4.
كم من الوقت يستغرق درس «مجموع المجموعة والتقسيم»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- حقيبة 0/1: خذ أو اترك
- حقيبة محسّنة من حيث المساحة
- برمجة ديناميكية للحقيبة غير المحدودة وتبديل العملات
- مجموع المجموعة والتقسيم