Das Teilmengensummenproblem 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 Elemente sich zur Zielsumme addieren.

PHP-Programm für Teilmengensummenproblem

Rekursive Lösung verwenden

Beispiel

 $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.";
?>

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 keine Teilmenge vorhanden ist Das ergibt zusammen 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

= $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 

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äre die Ausgabe des Codes Eine Teilmenge mit der angegebenen Summe gefunden.

Abschluss

Zusammenfassend gibt es zwei verschiedene Ansätze zur Lösung des Teilmengensummenproblems. 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.