A voir également:
- Macro de somme aléatoire pour resultat defini
- Telecharger macro convertir chiffre en lettre excel - Télécharger - Tableur
- Formule somme excel colonne - Guide
- Resultat foot - Télécharger - Vie quotidienne
- Somme si couleur - Guide
- Lexer resultat - Télécharger - Sport
5 réponses
Bonjour,
Le soucis c'est qu'il n'y a pas d'algorithme autre que celui d'explorer toutes les possibilités.
Et 400 valeurs c'est colossal. C'est exponentiel et le nombre explose très vite...
Si tu en as, supprime déjà toutes les valeurs > à la somme à atteindre, ça sera toujours ça de gagné.
A moins d'un coup de chance il va te falloir un temps considérable. Et tu ne peux te permettre d'arrêter dès qu'une solution est trouvée (imaginons un coup de bol et que tu aies une solution de moins de 10 termes qui présentent encore un temps de calcul raisonnable, enfin pour 400 valeurs ça serait plutôt moins de 5-6 termes...). Pour que le résultat soit fiable il faut que tu sois sûr qu'il n'y a pas une 2nde possibilité et il faut laisser tourner...
Bon courage.
Par curiosité fait moi savoir si tu as trouvé et en combien de temps, ou au bout de combien de temps tu as laissé tomber ;-)
Tu peux mettre en pause ce programme pour mettre en veille le PC et relancer plus tard.
https://mon-partage.fr/f/6wHR2xmh/
eric
Le soucis c'est qu'il n'y a pas d'algorithme autre que celui d'explorer toutes les possibilités.
Et 400 valeurs c'est colossal. C'est exponentiel et le nombre explose très vite...
Si tu en as, supprime déjà toutes les valeurs > à la somme à atteindre, ça sera toujours ça de gagné.
A moins d'un coup de chance il va te falloir un temps considérable. Et tu ne peux te permettre d'arrêter dès qu'une solution est trouvée (imaginons un coup de bol et que tu aies une solution de moins de 10 termes qui présentent encore un temps de calcul raisonnable, enfin pour 400 valeurs ça serait plutôt moins de 5-6 termes...). Pour que le résultat soit fiable il faut que tu sois sûr qu'il n'y a pas une 2nde possibilité et il faut laisser tourner...
Bon courage.
Par curiosité fait moi savoir si tu as trouvé et en combien de temps, ou au bout de combien de temps tu as laissé tomber ;-)
Tu peux mettre en pause ce programme pour mettre en veille le PC et relancer plus tard.
https://mon-partage.fr/f/6wHR2xmh/
eric
eriiic
Messages postés
24603
Date d'inscription
Statut
Contributeur
Dernière intervention
7 275
de rien !
yg_be
Messages postés
23541
Date d'inscription
Statut
Contributeur
Dernière intervention
Ambassadeur
1 584
bonjour,
Il existe une méthode très rapide pour réaliser cela.
termes de recherche: "programmation dynamique somme d'un sous ensemble"
Il y a de nombreux sites en français, pas toujours très abordables.
En anglais, voici un explication très claire, avec également des exemples de programmes:
https://www.geeksforgeeks.org/subset-sum-problem-dp-25/
Les programmes en exemple ne retournent pas la liste des solutions possibles, il faut légèrement les adapter pour récupérer cette liste.
Il existe une méthode très rapide pour réaliser cela.
termes de recherche: "programmation dynamique somme d'un sous ensemble"
Il y a de nombreux sites en français, pas toujours très abordables.
En anglais, voici un explication très claire, avec également des exemples de programmes:
https://www.geeksforgeeks.org/subset-sum-problem-dp-25/
Les programmes en exemple ne retournent pas la liste des solutions possibles, il faut légèrement les adapter pour récupérer cette liste.
ici, une méthode pour trouver toutes les sommes:
https://www.geeksforgeeks.org/perfect-sum-problem-print-subsets-given-sum/
https://www.geeksforgeeks.org/perfect-sum-problem-print-subsets-given-sum/
Bonjour,
attention quand même que le plus souvent trouver 1 somme valide n'est pas suffisant.
S'il s'agit d'attribuer des factures réglées par un paiement global, encore faut-il prouver que la solution trouvée est unique.
Sinon tu attribues le statut 'payé' à une mauvaise facture.
Et là ça devient très long s'il y a 400 valeurs. Récursivité ou pas, il faut tout explorer.
eric
attention quand même que le plus souvent trouver 1 somme valide n'est pas suffisant.
S'il s'agit d'attribuer des factures réglées par un paiement global, encore faut-il prouver que la solution trouvée est unique.
Sinon tu attribues le statut 'payé' à une mauvaise facture.
Et là ça devient très long s'il y a 400 valeurs. Récursivité ou pas, il faut tout explorer.
eric
la première étape est de choisir un algorithme adapté.
regarde bien ce que fait l'algorithme, il évite totalement la complexité combinatoire, et est très rapide. ni colossal, ni exponentiel.
tout son intelligence consiste à faire le minimum de calculs utiles, parfaitement adapté au problème de sommes de nombres positifs.
la seconde étape est, en effet, de le programmer pour l'environnement cible.
une fois l'algorithme choisi, tout programmeur VBA peut le programmer.
regarde bien ce que fait l'algorithme, il évite totalement la complexité combinatoire, et est très rapide. ni colossal, ni exponentiel.
tout son intelligence consiste à faire le minimum de calculs utiles, parfaitement adapté au problème de sommes de nombres positifs.
la seconde étape est, en effet, de le programmer pour l'environnement cible.
une fois l'algorithme choisi, tout programmeur VBA peut le programmer.
Bonjour,
je n'ai pas vraiment pu tester correctement vu que tu ne traites pas les nombres décimaux.
Les factures ont des centimes...
J'ai quand même lancé sur 40 valeurs, et enlevant la valeur négative que tu ne traites pas non plus. En dehors du fait que tes solutions sont entières donc erronées, que tu en trouves 27 et moi 119, tu mets 15 s contre 12s pour moi.
Bon, tes debug.print doivent y être pour beaucoup.
Entendons nous bien. Pour moi une amélioration c'est un gain conséquent comme les 3 min annoncées contre des heures ou des jours voire des années de calcul.
Je sais que je perd 10% de temps pour afficher la progression pour voir si ça vaut le coup de continuer et de donner la possibilité de suspendre et reprendre, de pouvoir passer certaines limites.
C'est un choix voulu. Pas grave de mettre 33s au lieu de 30s si on augmente les possibilités sur les plus gros problèmes.
J'ai quand même préparé un autre jeu de 27 données entières.
Tu trouves 28 solutions en 38s.
Mon programme s'est arrêté automatiquement au bout de 18s. Il avait déjà 240 solutions, maxi que je lui impose. Déjà que 2 solutions c'est une de trop, inutile d'en sortir des centaines.
Donc pas trop probant pour l'instant...
En fait tu te bases sur quoi pour dire que ma proposition n'est pas terrible et qu'on peut faire beaucoup mieux ?
Du concret après analyse sérieuse de mon code et avoir bien approfondi le problème ou au feeling ?
eric
je n'ai pas vraiment pu tester correctement vu que tu ne traites pas les nombres décimaux.
Les factures ont des centimes...
J'ai quand même lancé sur 40 valeurs, et enlevant la valeur négative que tu ne traites pas non plus. En dehors du fait que tes solutions sont entières donc erronées, que tu en trouves 27 et moi 119, tu mets 15 s contre 12s pour moi.
Bon, tes debug.print doivent y être pour beaucoup.
Entendons nous bien. Pour moi une amélioration c'est un gain conséquent comme les 3 min annoncées contre des heures ou des jours voire des années de calcul.
Je sais que je perd 10% de temps pour afficher la progression pour voir si ça vaut le coup de continuer et de donner la possibilité de suspendre et reprendre, de pouvoir passer certaines limites.
C'est un choix voulu. Pas grave de mettre 33s au lieu de 30s si on augmente les possibilités sur les plus gros problèmes.
J'ai quand même préparé un autre jeu de 27 données entières.
Tu trouves 28 solutions en 38s.
Mon programme s'est arrêté automatiquement au bout de 18s. Il avait déjà 240 solutions, maxi que je lui impose. Déjà que 2 solutions c'est une de trop, inutile d'en sortir des centaines.
Donc pas trop probant pour l'instant...
En fait tu te bases sur quoi pour dire que ma proposition n'est pas terrible et qu'on peut faire beaucoup mieux ?
Du concret après analyse sérieuse de mon code et avoir bien approfondi le problème ou au feeling ?
eric
comme déjà écrit, il suffit de tout multiplier par 100 si il y a des centimes.
je propose un algorithme pour lequel 400 valeurs n'est pas du tout colossal, un algorithme dont le temps de travail n'est pas exponentiel.
par exemple, il met 28 secondes pour trouver toutes les combinaisons dont la somme fait 360020 parmi les 400 nombres de 90000 à 90399.
si tu le souhaites, je peux tester l'algorithme sur d'autres ensembles et d'autres sommes.
je propose un algorithme pour lequel 400 valeurs n'est pas du tout colossal, un algorithme dont le temps de travail n'est pas exponentiel.
par exemple, il met 28 secondes pour trouver toutes les combinaisons dont la somme fait 360020 parmi les 400 nombres de 90000 à 90399.
si tu le souhaites, je peux tester l'algorithme sur d'autres ensembles et d'autres sommes.
Teste avec ce jeu de données : https://mon-partage.fr/f/WoZQ8D2P/
(c'est version beta en cours mais qui devrait être correcte)
Je trouve 119 solutions en 13s
Si tu trouves toutes les solutions en moitié moins je suis preneur ;-)
(c'est version beta en cours mais qui devrait être correcte)
Je trouve 119 solutions en 13s
Si tu trouves toutes les solutions en moitié moins je suis preneur ;-)
c'est instantané, pas le temps de mesurer le temps écoulé, largement moins qu'une seconde:
+574+136+938+500
+1438+574+136
+710+938+500
+710+1438
+136+574+938+500
+136+1438+574
+381+810+136+821
+381+136+810+821
+374+200+136+938+500
+374+200+1438+136
+374+200+136+938+500
+374+200+136+1438
+515+810+2+821
+195+632+821+500
+195+381+632+2+938
+195+515+938+500
+195+515+1438
+328+200+136+710+138+136+500
+328+374+810+136+500
+328+374+136+810+500
+328+195+200+381+136+632+2+138+136
+328+195+515+200+136+138+136+500
+243+810+138+136+821
+243+136+810+138+821
+243+136+810+2+136+821
+243+381+574+810+2+138
+243+374+574+136+821
+243+374+710+821
+243+374+136+574+821
+243+374+200+381+810+2+138
+243+195+632+2+138+938
+243+195+136+136+938+500
+243+195+136+1438+136
+243+195+515+374+821
+307+374+381+810+2+138+136
+307+374+381+136+810+2+138
+307+195+200+810+136+500
+307+195+200+136+810+500
+307+195+374+632+2+138+500
+307+328+381+632+500
+307+243+515+200+381+2+500
+307+243+328+632+138+500
+307+243+328+632+2+136+500
+307+243+328+136+632+2+500
+307+243+328+515+374+381
+537+195+374+136+632+138+136
+537+328+515+632+136
+537+328+515+136+632
+537+328+195+374+574+2+138
+537+243+515+200+381+136+136
+537+307+328+200+2+138+136+500
+537+307+328+200+136+2+138+500
+600+200+574+138+136+500
+600+200+710+138+500
+600+200+710+2+136+500
+600+200+136+138+136+938
+600+200+136+574+138+500
+600+200+136+574+2+136+500
+600+200+136+710+2+500
+600+195+200+381+632+2+138
+600+195+200+381+136+136+500
+600+195+515+200+138+500
+600+195+515+200+2+136+500
+600+195+515+200+136+2+500
+600+328+136+810+138+136
+600+328+374+710+136
+600+328+374+136+574+136
+600+328+374+136+710
+600+328+195+515+374+136
+600+328+195+515+374+136
+600+243+195+200+136+138+136+500
+600+307+195+200+710+136
+600+307+195+200+136+574+136
+600+307+195+200+136+710
+600+537+243+632+136
+600+537+243+136+632
+600+537+307+328+374+2
+1028+136+710+138+136
+1028+195+515+136+138+136
+1028+537+200+381+2
+1028+537+243+200+2+138
+1028+537+307+2+138+136
+1028+537+307+136+2+138
+684+243+200+381+2+138+500
+684+243+328+374+381+138
+684+243+328+374+381+2+136
+684+243+328+374+381+136+2
+684+307+381+2+138+136+500
+684+307+381+136+2+138+500
+684+307+200+136+821
+684+307+200+136+821
+684+307+200+381+574+2
+684+307+328+195+632+2
+684+307+243+200+574+2+138
+684+307+243+195+200+381+138
+684+307+243+195+200+381+2+136
+684+307+243+195+200+381+136+2
+684+537+515+136+2+138+136
+1129+381+138+500
+1129+381+2+136+500
+1129+381+136+2+500
+1129+243+2+138+136+500
+1129+243+136+2+138+500
+1129+243+200+574+2
+1129+243+195+200+381
+1129+307+574+138
+1129+307+574+2+136
+1129+307+710+2
+1129+307+136+574+2
+1129+307+374+200+138
+1129+307+374+200+2+136
+1129+307+374+200+136+2
+1129+307+195+381+136
+1129+307+195+381+136
+1129+307+195+515+2
+1129+307+243+195+138+136
+1129+307+243+195+136+138
+1129+307+243+195+136+2+136
+1129+684+195+2+138
nombre de solutions: 119
27 2148
0 secs
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
Si tu peux tester avec ce jeu de 400 valeurs maintenant stp
En théorie, 54 solutions
https://www.cjoint.com/c/KCuwKhuB75D
En théorie, 54 solutions
https://www.cjoint.com/c/KCuwKhuB75D
instantané aussi, le temps de calcul est proportionnel à 400*2148.
*** 400 2148
+710+938+500
+710+1438
+374+710+632+432
+514+381+432+821
+194+574+810+432+138
+194+374+810+632+138
+427+514+133+574+500
+427+194+514+381+632
+243+381+133+432+138+821
+243+374+710+821
+243+514+432+138+821
+243+194+514+133+632+432
+243+427+194+710+574
+243+427+194+381+133+632+138
+243+427+194+514+632+138
+306+710+632+500
+306+514+374+133+821
+306+194+710+938
+306+427+194+514+133+574
+537+194+133+710+574
+537+194+514+133+632+138
+537+427+374+810
+600+306+810+432
+600+537+243+194+574
+682+374+133+138+821
+682+427+194+133+574+138
+682+243+591+632
+682+600+306+427+133
+133+374+133+432+138+938
+133+427+381+133+574+500
+133+427+514+574+500
+133+243+381+432+138+821
+133+243+194+381+133+632+432
+133+243+194+514+632+432
+133+243+427+133+574+138+500
+133+243+427+194+381+632+138
+133+306+133+138+938+500
+133+306+133+1438+138
+133+306+374+133+632+432+138
+133+306+374+381+133+821
+133+306+514+374+821
+133+306+427+194+381+133+574
+133+306+427+194+514+574
+133+306+243+374+133+138+821
+133+306+243+427+194+133+574+138
+133+537+194+710+574
+133+537+194+381+133+632+138
+133+537+194+514+632+138
+133+600+194+514+133+574
+133+682+374+138+821
+133+682+194+133+574+432
+133+682+194+374+133+632
+133+682+427+194+574+138
+133+682+600+306+427
nombre de solutions: 54
400 2148
0 secs
Bonjour,
j'avoue que je commence à être sidéré, je ne pensais pas ça possible.
il va me falloir pas mal de temps pour essayer de comprendre.
Bon, il y a bien des cas où il mettra des heures voire des jours, mais comme c'est ceux où il y a des millions de solutions ce qui pour moi n'a plus de sens dans le type de problème visé, ce n'est pas un pb. On arrête des 10-20 trouvées et c'est bon.
Par contre j'aimerais bien retrouver le jeu de données où tu trouvais 28 solutions et moi beaucoup plus.
Je pense que c'est suite à une erreur de ma part car je n'ai pas réussi à mettre en défaut ton algorithme, mais j'aimerais en avoir le coeur net.
En tout cas merci pour cette ouverture plus que prometteuse :-)
eric
j'avoue que je commence à être sidéré, je ne pensais pas ça possible.
il va me falloir pas mal de temps pour essayer de comprendre.
Bon, il y a bien des cas où il mettra des heures voire des jours, mais comme c'est ceux où il y a des millions de solutions ce qui pour moi n'a plus de sens dans le type de problème visé, ce n'est pas un pb. On arrête des 10-20 trouvées et c'est bon.
Par contre j'aimerais bien retrouver le jeu de données où tu trouvais 28 solutions et moi beaucoup plus.
Je pense que c'est suite à une erreur de ma part car je n'ai pas réussi à mettre en défaut ton algorithme, mais j'aimerais en avoir le coeur net.
En tout cas merci pour cette ouverture plus que prometteuse :-)
eric
c'est grâce à toi que j'ai découvert tout cela.
en lisant "il n'y a pas d'algorithme autre que celui d'explorer toutes les possibilités", je me suis demandé si c'était vraiment vrai.
et j'ai découvert la programmation dynamique.
donc, merci à toi!
en lisant "il n'y a pas d'algorithme autre que celui d'explorer toutes les possibilités", je me suis demandé si c'était vraiment vrai.
et j'ai découvert la programmation dynamique.
donc, merci à toi!