تباين في مشكلة Knapsack: كيفية حل مشكلة Partition Equal Subset Sum في Java

تحديث: اقرأ عن تحسين تعقيد مساحة حل البرمجة الديناميكية في مقالتي للمتابعة هنا.

سابقًا ، كتبت عن حل مشكلة Knapsack (KP) مع البرمجة الديناميكية. يمكنك القراءة عنه هنا.

اليوم أريد أن أتحدث عن صيغة KP: قسم مجموع مشكلة مجموعة فرعية متساوية. لقد رأيت هذه المشكلة لأول مرة على Leetcode - وهذا ما دفعني للتعرف على KP والكتابة عنه.

هذه هي عبارة المشكلة (مستنسخة جزئيًا دون أمثلة):

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

للتعرف على بيان المشكلة الكاملة ، مع القيود والأمثلة ، تحقق من مشكلة Leetcode.

البرمجة الديناميكية

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

حل

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

الخطوة 1: حراسة ضد مجموع مجموعة غريبة

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

الخطوة 2: إنشاء الجدول

بعد ذلك ، نقوم بإنشاء الجدول.

تمثل صفوف الجدول مجموعة عناصر الصفيف التي يجب مراعاتها ، بينما تشير أعمدة الجدول إلى المبلغ الذي نريد الوصول إليه. قيم الجدول هي ببساطة قيم منطقية ، تشير إلى ما إذا كان يمكن الوصول إلى مجموع (عمود) بمجموعة من عناصر الصفيف (صف).

بشكل ملموس ، يمثل الصف i مجموعة من عناصر الصفيف من الفهارس 0 إلى (i-1). سبب هذا الإزاحة 1 لأن الصف 0 يمثل مجموعة فارغة من العناصر. لذلك ، يمثل الصف 1 عنصر الصفيف الأول (الفهرس 0) ، ويمثل الصف 2 أول عنصرين من الصفيف (الفهرس 0-1) ، وهكذا. في المجموع ، نقوم بإنشاء صفوف n + 1 ، بما في ذلك 0.

نريد فقط معرفة ما إذا كان يمكننا جمع ما يصل إلى نصف إجمالي إجمالي الصفيف بالضبط. لذلك نحن بحاجة فقط إلى إنشاء أعمدة totalSum / 2 + 1 ، بما في ذلك 0.

الخطوة 3: قبل ملء الجدول

يمكننا على الفور البدء في ملء الإدخالات للحالات الأساسية في جدولنا - الصف 0 والعمود 0.

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

في العمود الأول ، يجب أن يكون كل إدخال صحيحًا. يمكننا دائمًا ، بشكل تافه ، الوصول إلى مجموع مستهدف قدره 0 ، بغض النظر عن مجموعة العناصر التي يجب أن نعمل معها.

الخطوة 4: بناء الجدول (جوهر المشكلة)

يكون بعض الإدخال في الجدول في الصف i والعمود j صحيحًا (ممكن) إذا تم استيفاء أحد الشروط الثلاثة التالية:

  1. الإدخال في الصف i-1 والعمود j صحيح. أذكر ما يمثل رقم الصف. لذلك ، إذا تمكنا من الحصول على مبلغ معين مع مجموعة فرعية من العناصر التي لدينا في الوقت الحاضر ، فيمكننا أيضًا تحقيق ذلك المجموع مع مجموعة عناصرنا الحالية - ببساطة عن طريق عدم استخدام العناصر الإضافية. هذا تافه. دعنا نسمي هذا prevRowIsTrue.
  2. العنصر الحالي هو بالضبط المبلغ الذي نريد تحقيقه. هذا صحيح أيضا تافهة. دعنا نسمي هذا isExactMatch.
  3. إذا لم يتم استيفاء الشرطين المذكورين أعلاه ، فلدينا طريقة واحدة متبقية لتحقيق المبلغ المستهدف. هنا ، نستخدم العنصر الحالي - العنصر الإضافي في مجموعة العناصر في صفنا الحالي مقارنة بمجموعة العناصر في الصف السابق - ونتحقق من أننا قادرون على تحقيق ما تبقى من المبلغ المستهدف. دعنا نسمي هذا canArriveAtSum.

لنفك الشرط 3. لا يمكننا استخدام العنصر الحالي إلا إذا كان أقل من المبلغ المستهدف. إذا كانوا متساوين ، فسيتم تلبية الشرط 2. إذا كان حجمه أكبر ، فلا يمكننا استخدامه. لذلك ، فإن الخطوة الأولى هي التأكد من أن العنصر الحالي <المبلغ المستهدف.

بعد استخدام العنصر الحالي لدينا ، تبقى لدينا مع باقي المبلغ المستهدف. ثم نتحقق مما إذا كان ذلك ممكنًا عن طريق التحقق من الإدخال المقابل في الصف أعلاه.

كما هو الحال مع KP العادية ، نريد أن نبني تدريجياً طاولتنا من الأسفل إلى الأسفل. نبدأ بالحالات الأساسية ، حتى نصل إلى حلنا النهائي.

الخطوة 5: إرجاع الجواب

نحن ببساطة نعيد بساط الإرجاع [nums.length] [totalSum / 2].

رمز العمل

شكرا للقراءة!