Programme PHP pour le problème de la somme des sous-ensembles

Le problème de la somme des sous-ensembles est un problème classique en informatique et en programmation dynamique. Étant donné un ensemble d'entiers positifs et une somme cible, la tâche consiste à déterminer s'il existe un sous-ensemble de l'ensemble donné dont les éléments totalisent la somme cible.

Programme PHP pour le problème de somme de sous-ensembles

Utilisation d'une solution récursive

Exemple

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

Sortie

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

Dans l'exemple fourni, l'ensemble est [1, 7, 4, 9, 2] et les sommes cibles sont 16 et 25. Le deuxième appel avec une somme cible de 25 renvoie false, indiquant qu'il n'y a aucun sous-ensemble qui ajoute jusqu'à 25, donc la sortie est venue comme J'ai trouvé un sous-ensemble avec la somme donnée lors du premier appel. Aucun sous-ensemble avec la somme donnée lors du deuxième appel.

Temps pseudo-polynomial en programmation dynamique

Exemple

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

Sortie

Found a subset with given sum.

Dans l'exemple fourni, l'ensemble est [8, 15, 26, 35, 42, 59] et la somme cible est 50. L'appel de fonction isSubsetSum($set, $n, $sum) renvoie vrai, indiquant qu'il existe un sous-ensemble [8, 42] dans l'ensemble qui totalise la somme cible de 50. Par conséquent, la sortie du code serait Trouvé un sous-ensemble avec la somme donnée.

Conclusion

En conclusion, il existe deux approches différentes pour résoudre le problème de la somme des sous-ensembles. La première solution est une approche récursive qui vérifie s’il existe un sous-ensemble de l’ensemble donné avec une somme égale à la somme cible. Il utilise le retour en arrière pour explorer toutes les combinaisons possibles. Cependant, cette solution peut avoir une complexité temporelle exponentielle dans le pire des cas.

La deuxième solution utilise la programmation dynamique et résout le problème de la somme des sous-ensembles de manière ascendante. Il construit un tableau pour stocker les résultats intermédiaires et détermine efficacement s'il existe un sous-ensemble avec la somme donnée. Cette approche a une complexité temporelle de O(n*sum), ce qui la rend plus efficace que la solution récursive. Les deux approches peuvent être utilisées pour résoudre le problème de la somme des sous-ensembles, la solution de programmation dynamique étant plus efficace pour les entrées plus importantes.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!