Reconstituer des sous totaux

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: elephantstone

Bonjour à tous,

J'ai quelques souvenirs de maths, j'aurais dû m'y intéresser un peu plus "quand j'étais jeune"...

Et là j'ai un problème qui je suis sûr est mathématiquement solutionable.

Voilà: il s'agit d'une liste d'un peu plus de 600 enregistrements de dépenses (sous excel), chacun ayant une valeur. Et j'ai deux sous totaux, valeur A et B.

Sous excel (ou avec tt autre méthode) puis-je reconstituer les ou la combinaison de deux sous groupes d'enregistrement me donnant pour chacun une valeur A et B ?

Je ne sais pas trop où poster alors... merci pour votre aide !


Posted by: alben

Bonjour,
600 c'est beaucoup ! On peut déjà remarquer que si parmi ces valeurs, on en trouve deux identiques, soit elles sont dans la même partie (et ça reste soluble) soit elles sont dans les deux et ton problème devient insoluble.
Si on peut trouver, par exemple, trois valeurs dont la somme est égale à la somme de deux autres, c'est la même chose.
Tout dépend donc de la dispersion de tes nombres. Si tu as 600 valeurs avec trois ou quatre chiffres significatifs, le nombre de possibilités (j'appelle possibilité, une partition de tes valeurs en deux parties dont les totaux sont égaux à tes sous totaux) est extrèmement grand et je pense qu'il serait préférable de s'adresser à un sorcier...
Si tes nombres sont très dispersés et tes sous totaux très différents, c'est peut-être jouable


Posted by: elephantstone

Citation:
Posté par alben
Si tes nombres sont très dispersés et tes sous totaux très différents, c'est peut-être jouable


Merci Alben !

Effectivement ma dispersion est grande et mes sous totaux sont très différents. J'ai une feuille excel prête à t'envoyer si tu accepte d'y regarder d'un peu plus près...
Mais concernant la méthode statistique à appliquer, je suis totalement ignorant !
Je ne peut pas y aller "au feeling", car il y a évidemment un nombre de combinaisons que d'ailleurs je ne saurais pas non plus calculer...


Posted by: scelerat

Mettons qu'on veuille trouver un sous-ensemble de nombres positifs dont la somme vaut S. Il me semble que si S n'est pas trop grande, on peut faire un tableau de taille S, que l'on remplit progressivement. On considere l'element E1, on marque la case E1. On considere E2, on marque E2, et E1+E2, On prend E3, on marque E3 et toute case deja marquee + E3. La maniere de "marquer" doit permettre de retrouver la liste des elements qui ont permis d'arriver la. A la fin, il suffit de regarder si S est marquee, et de retrouver la(les) liste(s) correspondante(s).


Posted by: Flodelarab

Citation:
Posté par elephantstone
Je ne peut pas y aller "au feeling", car il y a évidemment un nombre de combinaisons que d'ailleurs je ne saurais pas non plus calculer...

600 valeurs et tu fais 2 groupes de cardinaux inconnus ?
Pour chacun des chiffres, tu décides si oui ou non il est dans le groupe 1. Si il ne l'est pas il est forcément dans le groupe 2

Soit 4$ 2^{600} répartitions possibles.










-