Table des matières
Utiliser une solution récursive
Exemple
Sortie
Conclusion
Maison développement back-end tutoriel php Programme PHP pour le problème de la somme des sous-ensembles

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

Sep 19, 2023 am 09:53 AM
php 问题 collecte d'enfants

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.";
?>
Copier après la connexion

Sortie

Found a subset with the given sum.
No subset with the given sum.
Copier après la connexion

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.";
?>
Copier après la connexion

Sortie

Found a subset with given sum.
Copier après la connexion

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!

Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Outils d'IA chauds

Undresser.AI Undress

Undresser.AI Undress

Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover

AI Clothes Remover

Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

Video Face Swap

Video Face Swap

Échangez les visages dans n'importe quelle vidéo sans effort grâce à notre outil d'échange de visage AI entièrement gratuit !

Outils chauds

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

SublimeText3 version Mac

Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Guide d'installation et de mise à niveau de PHP 8.4 pour Ubuntu et Debian Guide d'installation et de mise à niveau de PHP 8.4 pour Ubuntu et Debian Dec 24, 2024 pm 04:42 PM

PHP 8.4 apporte plusieurs nouvelles fonctionnalités, améliorations de sécurité et de performances avec une bonne quantité de dépréciations et de suppressions de fonctionnalités. Ce guide explique comment installer PHP 8.4 ou mettre à niveau vers PHP 8.4 sur Ubuntu, Debian ou leurs dérivés. Bien qu'il soit possible de compiler PHP à partir des sources, son installation à partir d'un référentiel APT comme expliqué ci-dessous est souvent plus rapide et plus sécurisée car ces référentiels fourniront les dernières corrections de bogues et mises à jour de sécurité à l'avenir.

7 fonctions PHP que je regrette de ne pas connaître auparavant 7 fonctions PHP que je regrette de ne pas connaître auparavant Nov 13, 2024 am 09:42 AM

Si vous êtes un développeur PHP expérimenté, vous aurez peut-être le sentiment d'y être déjà allé et de l'avoir déjà fait. Vous avez développé un nombre important d'applications, débogué des millions de lignes de code et peaufiné de nombreux scripts pour réaliser des opérations.

Comment configurer Visual Studio Code (VS Code) pour le développement PHP Comment configurer Visual Studio Code (VS Code) pour le développement PHP Dec 20, 2024 am 11:31 AM

Visual Studio Code, également connu sous le nom de VS Code, est un éditeur de code source gratuit – ou environnement de développement intégré (IDE) – disponible pour tous les principaux systèmes d'exploitation. Avec une large collection d'extensions pour de nombreux langages de programmation, VS Code peut être c

Expliquez les jetons Web JSON (JWT) et leur cas d'utilisation dans les API PHP. Expliquez les jetons Web JSON (JWT) et leur cas d'utilisation dans les API PHP. Apr 05, 2025 am 12:04 AM

JWT est une norme ouverte basée sur JSON, utilisée pour transmettre en toute sécurité des informations entre les parties, principalement pour l'authentification de l'identité et l'échange d'informations. 1. JWT se compose de trois parties: en-tête, charge utile et signature. 2. Le principe de travail de JWT comprend trois étapes: la génération de JWT, la vérification de la charge utile JWT et l'analyse. 3. Lorsque vous utilisez JWT pour l'authentification en PHP, JWT peut être généré et vérifié, et les informations sur le rôle et l'autorisation des utilisateurs peuvent être incluses dans l'utilisation avancée. 4. Les erreurs courantes incluent une défaillance de vérification de signature, l'expiration des jetons et la charge utile surdimensionnée. Les compétences de débogage incluent l'utilisation des outils de débogage et de l'exploitation forestière. 5. L'optimisation des performances et les meilleures pratiques incluent l'utilisation des algorithmes de signature appropriés, la définition des périodes de validité raisonnablement,

Comment analysez-vous et traitez-vous HTML / XML dans PHP? Comment analysez-vous et traitez-vous HTML / XML dans PHP? Feb 07, 2025 am 11:57 AM

Ce tutoriel montre comment traiter efficacement les documents XML à l'aide de PHP. XML (Language de balisage extensible) est un langage de balisage basé sur le texte polyvalent conçu à la fois pour la lisibilité humaine et l'analyse de la machine. Il est couramment utilisé pour le stockage de données et

Programme PHP pour compter les voyelles dans une chaîne Programme PHP pour compter les voyelles dans une chaîne Feb 07, 2025 pm 12:12 PM

Une chaîne est une séquence de caractères, y compris des lettres, des nombres et des symboles. Ce tutoriel apprendra à calculer le nombre de voyelles dans une chaîne donnée en PHP en utilisant différentes méthodes. Les voyelles en anglais sont a, e, i, o, u, et elles peuvent être en majuscules ou en minuscules. Qu'est-ce qu'une voyelle? Les voyelles sont des caractères alphabétiques qui représentent une prononciation spécifique. Il y a cinq voyelles en anglais, y compris les majuscules et les minuscules: a, e, i, o, u Exemple 1 Entrée: String = "TutorialSpoint" Sortie: 6 expliquer Les voyelles dans la chaîne "TutorialSpoint" sont u, o, i, a, o, i. Il y a 6 yuans au total

Expliquez la liaison statique tardive en PHP (statique: :). Expliquez la liaison statique tardive en PHP (statique: :). Apr 03, 2025 am 12:04 AM

Liaison statique (statique: :) ​​implémente la liaison statique tardive (LSB) dans PHP, permettant à des classes d'appel d'être référencées dans des contextes statiques plutôt que de définir des classes. 1) Le processus d'analyse est effectué au moment de l'exécution, 2) Recherchez la classe d'appel dans la relation de succession, 3) il peut apporter des frais généraux de performance.

Quelles sont les méthodes PHP Magic (__construct, __ destruct, __ call, __get, __set, etc.) et fournir des cas d'utilisation? Quelles sont les méthodes PHP Magic (__construct, __ destruct, __ call, __get, __set, etc.) et fournir des cas d'utilisation? Apr 03, 2025 am 12:03 AM

Quelles sont les méthodes magiques de PHP? Les méthodes magiques de PHP incluent: 1. \ _ \ _ Construct, utilisé pour initialiser les objets; 2. \ _ \ _ Destruct, utilisé pour nettoyer les ressources; 3. \ _ \ _ Appel, gérer les appels de méthode inexistants; 4. \ _ \ _ GET, Implémentez l'accès à l'attribut dynamique; 5. \ _ \ _ SET, Implémentez les paramètres d'attribut dynamique. Ces méthodes sont automatiquement appelées dans certaines situations, améliorant la flexibilité et l'efficacité du code.

See all articles