PHP-Programm für Teilmengensummenproblem

Das Teilmengensummenproblem ist ein klassisches Problem in der Informatik und dynamischen Programmierung. Bei einer gegebenen Menge positiver Ganzzahlen und einer Zielsumme besteht die Aufgabe darin, zu bestimmen, ob es eine Teilmenge der gegebenen Menge gibt, deren Elemente sich zur Zielsumme addieren.

PHP-Programm für Teilmengensummenproblem

Rekursive Lösung verwenden

Beispiel

<?php
// A recursive solution for the subset sum problem
// Returns true if there is a subset of the set
// with a sum equal to the given sum
function isSubsetSum($set, $n, $sum)
{
   // Base Cases
   if ($sum == 0)
      return true;
   if ($n == 0 && $sum != 0)
      return false;
   // If the last element is greater than the sum, then ignore it
   if ($set[$n - 1] > $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<br>";
else
   echo "No subset with the given sum<br>";
$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.";
?>

Ausgabe

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

Im bereitgestellten Beispiel ist die Menge [1, 7, 4, 9, 2] und die Zielsummen sind 16 und 25. Der zweite Aufruf mit einer Zielsumme von 25 gibt false zurück, was darauf hinweist, dass es keine Teilmenge gibt, die addiert bis 25. Die Ausgabe lautete also: Beim ersten Aufruf wurde eine Teilmenge mit der angegebenen Summe gefunden. Keine Teilmenge mit der angegebenen Summe im zweiten Aufruf.

Pseudopolynomiale Zeit mit dynamischer Programmierung

Beispiel

<?php
// A Dynamic Programming solution for
// subset sum problem
// Returns true if there is a subset of
// set[] with sun equal to given sum
function isSubsetSum( $set, $n, $sum)
{
	// The value of subset[i][j] will
	// be true if there is a subset of
	// set[0..j-1] with sum equal to i
	$subset = array(array());
	// If sum is 0, then answer is true
	for ( $i = 0; $i <= $n; $i++)
		$subset[$i][0] = true;
	// If sum is not 0 and set is empty,
	// then answer is false
	for ( $i = 1; $i <= $sum; $i++)
		$subset[0][$i] = false;
	// Fill the subset table in bottom
	// up manner
	for ($i = 1; $i <= $n; $i++)
	{
		for ($j = 1; $j <= $sum; $j++)
		{
			if($j < $set[$i-1])
				$subset[$i][$j] =
					$subset[$i-1][$j];
			if ($j >= $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 <= n; i++)
	{
	for (int j = 0; j <= sum; j++)
		printf ("%4d", subset[i][j]);
	printf("n");
	}*/
	return $subset[$n][$sum];
}
// Driver program to test above function
$set = array(8,15,26,35,42,59);
$sum = 50;
$n = count($set);
if (isSubsetSum($set, $n, $sum) == true)
	echo "Found a subset with given sum.";
else
	echo "No subset with given sum.";
?>

Ausgabe

Found a subset with given sum.

Im bereitgestellten Beispiel ist die Menge [8, 15, 26, 35, 42, 59] und die Zielsumme ist 50. Der Funktionsaufruf lautetSubsetSum($set, $n, $sum) Gibt „true“ zurück, was darauf hinweist, dass in der Menge eine Teilmenge [8, 42] vorhanden ist, die sich zur Zielsumme von 50 summiert. Daher würde die Ausgabe des Codes „Eine Teilmenge mit der angegebenen Summe gefunden“ lauten.

Fazit

Zusammenfassend lässt sich sagen, dass es zwei verschiedene Ansätze zur Lösung des Teilmengensummenproblems gibt. Die erste Lösung ist ein rekursiver Ansatz, der prüft, ob es eine Teilmenge der gegebenen Menge gibt, deren Summe der Zielsumme entspricht. Es nutzt Backtracking, um alle möglichen Kombinationen zu erkunden. Allerdings kann diese Lösung im schlimmsten Fall eine exponentielle Zeitkomplexität aufweisen.

Die zweite Lösung nutzt dynamische Programmierung und löst das Teilmengensummenproblem von unten nach oben. Es erstellt eine Tabelle zum Speichern von Zwischenergebnissen und ermittelt effizient, ob eine Teilmenge mit der angegebenen Summe vorhanden ist. Dieser Ansatz hat eine zeitliche Komplexität von O(n*sum) und ist damit effizienter als die rekursive Lösung. Beide Ansätze können zur Lösung des Teilmengensummenproblems verwendet werden, wobei die dynamische Programmierlösung für größere Eingaben effizienter ist.

Das obige ist der detaillierte Inhalt vonPHP-Programm für Teilmengensummenproblem. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!