PHP-Programm für Teilmengensummenproblem

Das Problem der Summe von Teilmengen ist ein klassisches Problem in der Informatik und der 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 Summe der Elemente der Zielsumme entspricht.

PHP-Programm für Teilmengen und Fragen

Verwenden Sie eine rekursive Lösung

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, deren Summe 25 ergibt. Die Ausgabe lautet also: Beim ersten Aufruf wurde eine Teilmenge mit der angegebenen Summe gefunden. Im zweiten Aufruf gibt es keine Teilmenge der angegebenen Summe.

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 beträgt die Menge [8, 15, 26, 35, 42, 59] und die Zielsumme beträgt 50. Der Funktionsaufruf isSubsetSum($set, $n, $sum) gibt true zurück, was angibt, dass es eine Teilmenge [8, 42] in der Menge gibt, die sich zur Zielsumme von 50 summiert. Der Code findet also die Teilmenge mit der angegebenen Summe.

Fazit

Zusammenfassend gibt es zwei verschiedene Möglichkeiten, das Teilmengensummenproblem zu lösen. Die erste Lösung ist ein rekursiver Ansatz, der prüft, ob es eine Teilmenge der gegebenen Menge gibt, deren Summe gleich der Zielsumme ist. Es verwendet 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 der Zwischenergebnisse und ermittelt effektiv, ob eine Teilmenge mit einer bestimmten Summe vorhanden ist. Dieser Ansatz hat eine Zeitkomplexität von O(n*sum) und ist effizienter als die rekursive Lösung. Beide Methoden 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!