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

برنامج PHP لمشكلة مجموع المجموعات الفرعية

استخدام الحل العودي

مثال

 $sum)
      return isSubsetSum($set, $n - 1, $sum);
   // Check if the sum can be obtained by either including or excluding the last element
   return isSubsetSum($set, $n - 1, $sum) ||
      isSubsetSum($set, $n - 1, $sum - $set[$n - 1]);
}
// Driver Code
$set = array(1, 7, 4, 9, 2);
$sum = 16;
$n = count($set);
if (isSubsetSum($set, $n, $sum) == true)
   echo "Found a subset with the given sum
";
else
   echo "No subset with the given sum
";
$sum = 25;
$n = count($set);
if (isSubsetSum($set, $n, $sum) == true)
   echo "Found a subset with the given sum.";
else
   echo "No subset with the given sum.";
?>

الإخراج

Found a subset with the given sum.
No subset with the given sum.

في المثال المقدم، المجموعة هي [1، 7، 4، 9، 2]، والمجاميع المستهدفة هي 16 و25. الاستدعاء الثاني ذو المبلغ المستهدف 25 يُرجع خطأ، مما يشير إلى عدم وجود مجموعة فرعية يضيف ما يصل إلى 25. لذلك جاء الإخراج كما تم العثور على مجموعة فرعية مع المبلغ المحدد في المكالمة الأولى. لا توجد مجموعة فرعية مع المبلغ المحدد في المكالمة الثانية.

زمن متعدد الحدود الزائف باستخدام البرمجة الديناميكية

مثال

= $set[$i-1])
				$subset[$i][$j] =
					$subset[$i-1][$j] ||
					$subset[$i - 1][$j -
							$set[$i-1]];
		}
	}
	/* // uncomment this code to print table
	for (int i = 0; i 

الإخراج

Found a subset with given sum.

في المثال المقدم، المجموعة هي [8, 15, 26, 35, 42, 59]، والمجموع المستهدف هو 50. استدعاء الدالة هوSubsetSum($set, $ n, $sum) يُرجع صحيحًا، مما يشير إلى وجود مجموعة فرعية [8, 42] في المجموعة التي يضيف ما يصل إلى المبلغ المستهدف وهو 50. ولذلك، سيتم العثور على إخراج التعليمات البرمجية مجموعة فرعية مع المبلغ المحدد.

خاتمة

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

يستخدم الحل الثاني البرمجة الديناميكية ويحل مشكلة مجموع المجموعة الفرعية بطريقة تصاعدية. يقوم بإنشاء جدول لتخزين النتائج المتوسطة ويحدد بكفاءة ما إذا كانت هناك مجموعة فرعية بالمجموع المحدد. يحتوي هذا النهج على تعقيد زمني قدره O(n*sum)، مما يجعله أكثر كفاءة من الحل العودي. يمكن استخدام كلا الطريقتين لحل مشكلة مجموع المجموعة الفرعية، حيث يكون حل البرمجة الديناميكية أكثر كفاءة للمدخلات الأكبر.