méthode pour trouver un sous-ensemble

[danyvio]

De surcrpoît, quand on a trouvé un sous-ensemble à somme nulle, on obtient de fait un sous ensemble complémentaire, lui aussi à somme nulle.
-----

[invite4492c379]

Hello,

oui en effet, mais malgré tout cela ne réduit l'espace de recherche que de moitié. Si on reprend les spec de Céline2, il peut y avoir 1000 occurences réparties sur 30 valeurs positives et 30 négatives (on ne prend pas les 0 en compte ici). Au pire il y aura environ 17 occurences par valeurs, soit de l'ordre de 17³⁰ combinaisons ~ 8.10³⁶, en réduisant par 2 pour chacun des deux ensembles on aboutit en tout à 2x4.10³⁶ combinaisons à parcourir. La valeur maximum d'une somme sera 500*30=1500 (sinon il ne reste pas assez d'occurences dans l'autre liste pour faire la même somme).
On a L la liste d'origine, L+ la liste des positifs, L- la liste des négatifs. Il semble raisonnable de se dire que l'on peut construire une liste de hashage H+ (resp H-) qui à une somme associe les combinaisons de L+ (resp. L-) qui ont cette somme. Cela suit en quelquesorte l'idée de l'algorithme que Céline2 a débusqué.
Intuitivement je me dis : 1500 valeur de somme, 10³⁶ combinaisons ... il doit y avoir une tonne de solution !

[invite4492c379]

Évidemment dans mon message précédent il faut remplacer les 1500 par des 15000.