combinaisons devant donner un total [RESOLU]

[gosselien]

Bonjour ou bonsoir, c'est selon...

un ex-collègue me pose le problème suivant (assez tordu je trouve mais bon...)

Un fournisseur paye 2850€ pour des factures mais sans nous préciser quelles factures sur les 10 qu'il y a en attente, de régularisation il a payé...

Il faut donc (et c'est rare heureusement) trouver les différentes combinaisons pour arriver à ce total en regard des montants de chacune des factures; dans l'exemple que j'envoie ici, ce sont des chiffres ronds qui donnent au minimum 3 combinaisons, je n'ai pas cherché plus loin, il est certain qu'avec des chiffres avec décimales et non arrondis, il y aura peu de combinaisons...

Merci de votre aide VBA, car moi, je ne suis pas capable de résoudre ce problème et si je pouvais avoir des commentaires dans le code VBA, ça ne pourrait que m'aider

P.

 

[gosselien]

Re : combinaisons devant donner un total [RESOLU]

re,

Je ne peux qu'applaudir à 2 mains !!!

J'ai re(gardé) les 2 codes ainsi que les autres propositions mais celle de Roger2327 est la plus fun et complexe

Merci pour ceux qui en ont besoin dans leur boulot
P.

 

[ROGER2327]

Re : combinaisons devant donner un total [RESOLU]

Suite...

... avec deux versions plus rapides : 0,3 s environ pour vingt données ; 16 s pour vingt-six données.
Je ne pense pas pouvoir aller plus vite avec cette méthode.​

Bonne journée.


ℝOGER2327
#7733

Lundi 9 Gueules 142 (Sainte Crêpe, laïque - fête Suprême Quarte)
15 Pluviôse An CCXXIII, 4,4869h - vache
2015-W06-2T10:46:07Z

 

[eriiic]

Re : combinaisons devant donner un total [RESOLU]

Bonjour,

Sans vouloir défendre à tout crins ma version qui est moins rapide que celle de roger (y'a pas photo), à moment donné j'ai dû faire un choix.
Pour les listes longues soit laisser allumé le micro plusieurs jours, soit accepter un ralentissement (le formulaire) et donner la possibilité de mettre en pause pour mettre le micro en veille, en plus d'avoir une vision de l'évolution.
Mais la concision du code de roger est phénoménale. Pas mieux... ;-)
Tu devrais peut-être l'étendre pour permettre plus 26 valeurs ? Après tout, si l'utilisateur est disposé à attendre pour avoir son résultat.
eric

 

[gosselien]

Re : combinaisons devant donner un total [RESOLU]

Salut à tous,

2 remarques pour moi:

1) le projet de Roger2327 est top et il n'en faut pas plus pour mon cas , merci encore .. (j'ai d'ailleurs mis [RESOLU] dans le titre), il intéresse à présent ma compagne pour une chose à peu près similaire mais avec un critère en plus, j'attends plus de détails.
2) la vitesse, même si elle était "lente", serait plus rapide que de chercher à la mimine , et accessoirement, cette vitesse dépends bien sur du nombre de combinaisons ET de l'âge/puissance/mémoire etc... du pc.
Je vais d'ailleurs tester sur un MAC plus récent, mais pour comparer il faudrait aussi que plusieurs ici prennent le même tableau et indiquer ses résultats

Patrick

 

[ROGER2327]

Re : combinaisons devant donner un total [RESOLU]

Re...

Bonjour,

Sans vouloir défendre à tout crins ma version qui est moins rapide que celle de roger (y'a pas photo), à moment donné j'ai dû faire un choix.
Pour les listes longues soit laisser allumé le micro plusieurs jours, soit accepter un ralentissement (le formulaire) et donner la possibilité de mettre en pause pour mettre le micro en veille, en plus d'avoir une vision de l'évolution.
Mais la concision du code de roger est phénoménale. Pas mieux... ;-)
Tu devrais peut-être l'étendre pour permettre plus 26 valeurs ? Après tout, si l'utilisateur est disposé à attendre pour avoir son résultat.
eric

Comme je l'ai déjà dit, j'emploie une méthode des plus rustiques qui consiste à essayer toutes les combinaisons de termes, avec un seul « raffinement » : abandon du calcul d'une somme dès que la somme partielle excède la somme recherchée.
Cette méthode implique le doublement du temps de calcul chaque fois qu'on ajoute un terme dans la colonne Montant. Elle ne saurait donc s'appliquer pour un grand nombre d'items.

D'autre part, le cœur de la procédure est la boucle

      For i = 1 To 2 ^ UBoDat - 1
         'Code
      Next

i étant un entier de type Long, il ne peut excéder 2 147 483 647, i.e. exactement 2[SUP]31[/SUP] - 1. Par conséquent UBoDat, qui est le nombre d'items à traiter, ne peut être supérieur à 31. Encore faut-il encadrer cette boucle par On Error Resume Next et On Error GoTo 0, faute de quoi la sortie de la dernière boucle provoque une erreur par dépassement de capacité...
Ceux qui possède une version « 64 bits » d'Excel pourront peut-être aller plus loin avec le type « LongLong ».

Étendre le tableau à plus de vingt-six lignes ne pose pas de problème technique : il suffit d'insérer des lignes dans le tableau ; le code n'a pas à être modifié.

On peut automatiser la chose avec la procédure NombreDeLignes qu'on trouvera dans le classeur joint à ce message. Dans ce classeur, j'ai repris les procédures de la pièce jointe #17 (Onglet 1 et Onglet 1x) en les optimisant au mieux que j'ai pu. Avec l'échantillon de 31 données pour trouver la somme de 2i327 que j'y ai mis, il faut attendre 426 s pour voir le résultat. C'est mieux que la version précédente qui demande 485 s.
Et ce n'est pas trop mal si l'on a conscience que plus de deux milliards de boucles sont exécutées.[SUP][1][/SUP]

Mais on ne voit le résultat qu'à la fin de l'exécution de la procédure, et toute interruption prématurée renvoie un tableau vide. Gênant...

J'ai donc ajouté deux onglets (Onglet 2 et Onglet 2x) donnant un affichage progressif. C'est évidemment au prix de la dégradation de la vitesse d'exécution : avec les même données, il faut 462 s.

Tant qu'à modifier, j'en ai profité pour ajouter la procédure NombreDeLignes, associée au raccourci Ctrl l et une procédure Efface (raccourci Ctrl Q) pour vider les résultats. Ces procédures sont dans le module standard Module01.

Enfin, j'ai ajouté dans chaque module de feuille un chronométrage (procédure test) pour me faciliter la mise au point. Si on ne veut pas de chronométrage, il suffit de remplacer test par toto dans la procédure :

Private Sub Worksheet_BeforeDoubleClick(ByVal Cible As Range, Contremander As Boolean)
   If Cible.Address = [Total_reçu].Address Then Contremander = True: test
End Sub

et de supprimer la procédure test.

Il ne me reste plus qu'à deviner à quoi peut bien servir ce truc...
​

Bonne soirée.


[SUP][1][/SUP] La durée d'exécution dépend évidemment des données et de la somme à trouver.
Avec 31 données, la durée d'exécution varie de 4 min à trois quarts d'heure selon la somme à trouver.

ℝOGER2327
#7737

Vendredi 13 Gueules 142 (Copulation - Vacuation)
19 Pluviôse An CCXXIII, 7,6159h - pulmonaire
2015-W06-6T18:16:42Z

 

[eriiic]

Re : combinaisons devant donner un total [RESOLU]

Bonjour,

En plus il y a le choix, beau travail
Au début aussi j'avais essayé de faire le minimum pour pouvoir en traiter le maximum. Et au fil des demandes ça glisse, jusqu'à l'erreur ultime : le formulaire... :-s

Tu devais être content hier, c'était LE jour (Vendredi 13 Gueules 142 (Copulation - Vacuation)) ;-)

Bon dimanche à tous
eric

PS : Il ne me reste plus qu'à deviner à quoi peut bien servir ce truc..
On te règle en 1 paiement certaines factures sans te dire lesquelles, tu sais juste qu'on t'a réglé 123.45 €.

 

[mapomme]

Re : combinaisons devant donner un total [RESOLU]

Bonjour gosselien, ROGER2327, job75, Modeste geedee, eriiiic

Bon, j'y vais aussi avec ma petite proposition.

J'étais parti sur un algo basé sur la récursivité mais j'atteignais vite les limites de la capacité de la pile d'appel. J'ai donc transformé l'algo en boucle. Il y a un traitement pour les positifs (triés en ordre décroissant) qui permet de ne pas parcourir toutes les combinaisons. C'est une pile où on n'empile que les factures qui pourraient faire partie d'une solution; les autres sont écartées.

Pour introduire les factures négatives (ou avoirs), on se ramène à boucler N fois sur les factures positives. Il y a autant de passage dans la boucle que de combinaisons N de factures négatives. A chaque passage, on rajoute à la somme cible initiale, la valeur absolue des montants de la combinaison considérée parmi les factures négatives.

Le traitement a l'air assez rapide. On pourrait encore optimiser plus par le traitement amélioré des doublons de factures (ou avoirs) à montants identiques.

J'ai repris la présentation de Roger2327 pour la Source mais transposer l'affichage dans une feuille "Result". Ceci permet d'afficher plus de combinaisons. La sélection d'une cellule au sein du tableau "Result" surligne les en-têtes des factures de la combinaison au sein de la ligne de la cellule.

A priori, on peut dépasser les 31 factures (Test 06). Par contre, vu la méthode employée pour trouver les combinaisons des avoirs, le nombre des factures négatives (ou avoirs) est limité à 511. Les avoirs augmentent vite les temps d'exécution.

Pour la vérification des montants des combinaisons, la colonne B sur la feuille résultat s'en charge.
Pour le nombre de combinaisons, je trouve apparemment les mêmes valeurs que Roger2327 .

Je n'ai pas poussé plus loin les vérifs. Si ça se trouve, il y a le gros bogue évident que je n'ai point vu et qui aurait dû me sauter aux yeux.

edit: v2b (uniquement quelques modif. esthétiques + un meilleur retour à l'option excel 'calcul automatique')

 

[eriiic]

Re : combinaisons devant donner un total [RESOLU]

Bonjour tout le monde,

On pourrait encore optimiser plus par le traitement amélioré des doublons de factures (ou avoirs) à montants identiques.

J'avais mis cette option un temps, mais en fait non. On élimine des solutions valables.

eric

 

[gosselien]

Re : combinaisons devant donner un total [RESOLU]

Bonsoir;

en tous cas, vous êtes forts ! c'est comique aussi de voir que tout le monde essaye de gagner 1/20 seconde

j'ai ici une autre (vieille version, un peu modifiée et imparfaite) qui ne fonctionne pas si vite mais bon...
doit-on courir après le temps s'il y a 20 factures ?

P.

 

[DIDOUS59270]

Bonjour roger2327

J' ai besoin de votre aide concernant des macros sur excel
pouvez vous me contacter directement?