Discussion :

[senacle]

Bonjour,

Soit une somme S = 270.
Soit 9 nombres qui varient de 0 à S.
Quelle est la liste des 9 nombres dont la somme est <= S ?

Par exemple
270 0 0 0 0 0 0 0 0
269 0 0 0 0 0 0 0 0
269 1 0 0 0 0 0 0 0
269 0 1 0 0 0 0 0 0
...
268 0 0 0 0 0 0 0 0
....
268 1 1 0 0 0 0 0 0
268 1 0 1 0 0 0 0 0
....
268 0 1 1 0 0 0 0 0
268 0 1 0 1 0 0 0 0
.....
15 0 0 0 0 0 0 0
36 0 25 0 18 0 0 0 0
.....
0 0 0 0 269 0 0 0 0
0 0 0 0 269 1 0 0 0
....

La position du nombre dans la ligne est à prendre en compte.
269 1 0 0 0 0 0 0 0
0 0 0 0 269 1 0 0 0
sont deux combinaisons qui doivent être conservées.

Pour l'instant, j'ai fait une boucle récursive qui génèrent toutes les combinaisons des 9 nombres.
Je teste à chaque fois leur somme.
Si <= S, je garde.

Mais ça fait 270⁹ combinaisons à tester......

Y aurait-il plus rapide pour trouver les combinaisons qui satisfont à la somme sans tester toutes les combinaisons ?

[Flodelarab]

Bonjour

Chaque nombre est ou n'est pas dans la combinaison finale. Donc 2 cas possibles pour chaque 9 nombres, soit 2⁹=512 valeurs possibles.

Vu l'énoncé, je les écrirais tous (les 512) et je supprimerais ceux qui dépassent S, en prenant ceux qui ont 9 nombres puis ceux qui ont 8 nombres (sous-ensemble du précédent), puis ceux qui ont 7 nombres (sous-ensemble du précédent), puis 6, puis 5, puis 4, etc

[senacle]

Chacun des 9 nombres peut valoir entre 0 et 270.
Et on peut avoir plusieurs fois le même nombre sur chaque ligne.

J'ai compété mon premier post :
La position du nombre dans la ligne est à prendre en compte.
269 1 0 0 0 0 0 0 0
0 0 0 0 269 1 0 0 0
sont deux combinaisons qui doivent être conservées.

[pseudocode]

Bonjour,

Y aurait-il plus rapide pour trouver les combinaisons qui satisfont à la somme sans tester toutes les combinaisons ?

Comme on le voit dans ton exemple, on s'aperçoit assez vitre qu'on peut décomposer la liste.

Si on appelle SubsetSum(N,S) les listes de N nombres dont la somme est égale à S, alors

SubsetSum(9,270) = {SubsetSum(1,270) X SubsetSum(8, 0)}, {SubsetSum(1,269) X SubsetSum(8, 1)}, {SubsetSum(1,268) X SubsetSum(8, 2)}, ...

Ou, d'une manière générale

SubsetSum(N,S) = SubsetSum(N-i,S-k) X SubsetSum(i,k) pour k parcourant [0,S], et i une valeur arbitraire dans [0,N]

avec
SubsetSum(0,a) = vide
SubsetSum(1,a) = {a}


Ca nous fait donc un tableau de S*N listes à remplir par récursion, puis un algo assez simple pour "piocher" les bonnes cases du tableau.

[senacle]

Si on appelle SubsetSum(N,S) les listes de N nombres dont la somme est égale à S

J'avais bien regardé du côté de l'algorithme SubsetSum, mais il ne fait que pour =.
Je cherche <=

SubsetSum(N,S) = SubsetSum(N-i,S-k) X SubsetSum(i,k)

Comment traduire X ? C'est un produit de matrices ?

un tableau de S*N listes à remplir

J'ai déjà fait un essai avec ma méthode avec les 9 nombres valant 0 ou 30, j'obtiens 48 556 combinaisons à retenir.

0 0 0 0 0 0 0 0 30
0 0 0 0 0 0 0 30 0
0 0 0 0 0 0 0 30 30
0 0 0 0 0 0 30 0 0
0 0 0 0 0 0 30 0 30
0 0 0 0 0 0 30 30 0
0 0 0 0 0 0 30 30 30
......
30 30 30 30 30 30 30 30 30


Ca ne représente qu'une partie de ce dont j'ai besoin ( rappel : les 9 nombres valent entre 0 et 270).
On est donc loin des S*N = 270*9 = 2430.

[pseudocode]

J'avais bien regardé du côté de l'algorithme SubsetSum, mais il ne fait que pour =.
Je cherche <=

Si tu as une solution pour la somme exacte, les solutions de ton problème ont forcément des coordonnées inférieures:

Solution Somme=270 --> (200,60,10,0,0,0,0,0,0)

Solution Somme<=270 --> ([0-200],[0-60],[0-10],0,0,0,0,0,0)

Comment traduire X ? C'est un produit de matrices ?

Un produit cartésien: {a,b} x {1,2} = (a,1), (a,2), (b,1), (b,2)

Ca ne représente qu'une partie de ce dont j'ai besoin ( rappel : les 9 nombres valent entre 0 et 270).
On est donc loin des S*N = 270*9 = 2430.

Aucune méthode ne va diminuer le nombre de solutions à ton problème.
Là je proposais juste de construire les solutions finales en concaténant les solutions intermédiaires pour que ce soit plus rapide.
Mais le nombre de solution de solutions à ton problème reste de toutes façons très grand (cf. "Partition d'un entier" sur wikipedia).

[senacle]

Si tu as une solution pour la somme exacte, les solutions de ton problème ont forcément des coordonnées inférieures:

Solution Somme=270 --> (200,60,10,0,0,0,0,0,0)

Solution Somme<=270 --> ([0-200],[0-60],[0-10],0,0,0,0,0,0)

OK, compris.


Je vais essayer de créer le code en php.

(cf. "Partition d'un entier" sur wikipedia).

En fait, ce serait plutôt la composition d'un entier dans mon cas : l'ordre est important.
https://fr.wikipedia.org/wiki/Compos...ombinatoire%29