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

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

Sortir

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 pas de sous-ensemble cela fait 25, donc le résultat est venu 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

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

Sortir

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.