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 la somme des éléments est égale à la somme cible.

Programme PHP pour les sous-ensembles et les questions

Utiliser 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'existe aucun sous-ensemble dont la somme est égale à 25. La sortie est donc Found un sous-ensemble avec la somme donnée lors du premier appel. Il n'y a aucun sous-ensemble de la somme donnée dans le deuxième appel.

Temps pseudopolynomial utilisant la 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 true, indiquant qu'il existe un sous-ensemble [8, 42] dans l'ensemble qui totalise la somme cible de 50. Le code trouvera donc le sous-ensemble avec la somme donnée.

Conclusion

En résumé, il existe deux manières différentes de 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é dont la somme est égale à la somme cible. Il utilise le backtracking 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 une somme donnée. Cette approche a une complexité temporelle de O(n*sum) et est plus efficace que la solution récursive. Les deux méthodes 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!