Discussion :

[albano06]

bonjour a tous
voila mon problème ;
j'ai une liste de nombre S; et je doit trouver 2 listes secondaires S1 et S2 égale entre elle ( la somme des valeurs de S1 doit être égale a la somme des valeurs de S2 ) comprenant toutes les valeurs de la liste S
Si S1=S2 n'existe pas alors je doit trouver S1 le plus proche possible de S2


Je ne vois pas comment faire cet algorithme sans un algorithme glouton qui consomme beaucoup de ram ; y a t'il un moyen de la faire sans consommer autant ?

Merci de votre aide

[François DORIN]

Bonjour,

Est-ce que les nombres sont des nombres entiers ? Si oui, une condition nécessaire (mais pas suffisante), c'est que la somme des éléments de ta liste soit paire. Mieux : tu connais la somme de tes listes S1 et S2 ! Se sera la somme des éléments de ta liste initiale divisée par 2.

Il ne te reste alors qu'une seule liste à faire. La seconde sera établie automatiquement avec les éléments restants.

Ensuite, la première idée qui me vient est de tester toutes les solutions possibles. Bien entendu, il faut le faire intelligemment ! Je commencerais par trier la liste des éléments, et à rajouter les éléments au fur et à mesure dans la liste S1 en commençant par les plus gros.


Je vois le second algorithme comme un dérivé du premier. Au lieu de chercher S/2, on cherche une liste minimisant S/2 - S1.

[albano06]

Est-ce que les nombres sont des nombres entiers ? Si oui, une condition nécessaire (mais pas suffisante), c'est que la somme des éléments de ta liste soit paire. Mieux : tu connais la somme de tes listes S1 et S2 ! Se sera la somme des éléments de ta liste initiale divisée par 2.

Oui les nombre sont entiers ; la somme des éléments de la liste n'est pas obligatoirement paire ; si elle est impaire on rajoute un +1 a S1 ou S2

rajouter les éléments au fur et à mesure dans la liste S1 en commençant par les plus gros.

j'ai déjà fait ça dans mon algorithme mais le problème c'est que avec cette méthode le bon résultat n'est pas toujours trouvé ; j'avais pensé a réaliser un algorithme en plusieurs étapes qui après un premier algorithme affiche un premier résultat et lance un deuxième algorithme et affiche un autre résultat si il est plus pertinent

on cherche une liste minimisant S/2 - S1

je ne vois pas du tous comment faire cela





pour l'instant j'ai réalisé ce début de "pré"algorithme

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
S=(X1,X2,X3,...,Xn)		# j'appelle X les valeurs dans le vecteur S
sort S				#je trie dans l'ordre croissant les valeurs du vecteur S
E=somme des Xn 			# je fais la somme de toutes les valeurs X du vecteur 
si E%%2=0 alors :		#si E est pair alors je cherche somme S1 = somme S2 ; si S1=S2 n'existe pas (comme ici )alors je cherche S1 et S2 le plus proche possible 
S1=somme de X1 a Xn-1		#S1= somme de toutes les valeurs sauf la dernière		
S2=Xn				#S2= la dernière valeur du vecteur ( la plus grande parce que on a fait un sort au debut )
Si S1=S2 FINI
si S2>S1 FINI			# S2= la plus grande valeur du vecteur et S1= toute les autre valeur du vecteur   ; on peut donc pas faire mieux
si S2<S1 faire :
tant que S2<S1 faire :
	n=n+1
	S2=S2+Xn		# on ajoute a S2 la plus petite valeur du vecteur 
	S1=S1-Xn		#on retire a S1 la plus petites valeur du vecteur
 
si S2=S1 FINI
si S2>S1 faire :

[tbc92]

Es-tu dans un cadre scolaire, ou dans un cadre autre. Si tu es dans un cadre autre, tu peux avoir des informations complémentaires.
Si, dans une configuration moyenne, tu as 1000 nombres dont la somme fait 100 000, ou si tu as 1000 nombres dont la somme fait 10 000 000, la stratégie est probablement différente.
Dans l'hypothèse 1, il y a certainement une solution pour que les 2 sous-listes fassent 50 000. Mais dans l'hypothèse 2, c'est moins probable. Et donc des algo quipeuvent être différents selon les

Ca, c'est une chose.

Mais 'autre chose plus importante, c'est de corriger ce que tu écris.

Tu écris : j'ai déjà fait ça dans mon algorithme mais le problème c'est que avec cette méthode le bon résultat n'est pas toujours trouvé ;

Dans la proposition de Dorinf, il y avait des trucs sous-entendus. Tape Parcours d'arbre informatique, ou bien arbre binaire ou des trucs comme ça sur Google, tu y verras plus clair, et tu comprendras mieux ce qu'il suggère.

[pseudocode]

Tape Parcours d'arbre informatique, ou bien arbre binaire ou des trucs comme ça sur Google, tu y verras plus clair, et tu comprendras mieux ce qu'il suggère.

Tant que tu y es , tapes "Partition problem" dans wikipedia.

[François DORIN]

Oui les nombre sont entiers

Très bon à savoir ça !

la somme des éléments de la liste n'est pas obligatoirement paire ; si elle est impaire on rajoute un +1 a S1 ou S2

Ca ne veut rien dire. Tu cherches à faire en sorte que S1 et S2 soit le plus proche possible, c'est ça ?

j'ai déjà fait ça dans mon algorithme mais le problème c'est que avec cette méthode le bon résultat n'est pas toujours trouvé ; j'avais pensé a réaliser un algorithme en plusieurs étapes qui après un premier algorithme affiche un premier résultat et lance un deuxième algorithme et affiche un autre résultat si il est plus pertinent

Il ne s'agit pas de construire une unique solution et de voir si elle convient, il s'agit de les explorer toutes mais en choisissant l'ordre d'exploration. tbc92 et pseudocode t'ont donné des pistes quant au nom des problèmes se rapprochant du tien.

on cherche une liste minimisant S/2 - S1
je ne vois pas du tous comment faire cela

Si tu parcours l'ensemble des possibilités, faire ce calcul est très simple. La première étape est donc de résoudre le problème initial, avant de résoudre le second.

[Pascaltech]

Bonjour,

En utilisant la démarche d'un botaniste : "identifier - ranger- exploiter" tu peux obtenir un résultat assez précis.

Identifer : calcules le rapport entre chaque valeur et le 100ème(ou 1000ème selon la précision souhaitée) du total cible
Ranger : ranges chaque valeur par rapport correspondant
Manipuler : ajoutes chaque valeur selon son rapport pour obtenir le total désiré.

Ex : 20/100 + 30/100 + 50/100 = total

Considère comme total cible S1 + S2.

[nono_31]

Bonjour Albano06,

Je parierais qu'il s'agit du projet de programmation d'Albano06 à l'UNS

C'est une bonne initiative de demander de l'aide, et de t'être inscrit sur le site.

Cela serait encore mieux de lire d'abord les ressources mises à ta disposition dans le cadre du projet (notamment les pages wikipedia).

Je ne vois pas comment faire cet algorithme sans un algorithme glouton qui consomme beaucoup de ram ; y a t'il un moyen de la faire sans consommer autant ?

Justement, les gloutons sont rapides et peu gourmands, généralement, au détriment de l'exactitude.