combinaisons devant donner un total [RESOLU]

gosselien

XLDnaute Barbatruc
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.
 

Pièces jointes

  • combinaisons.xlsm
    10 KB · Affichages: 88
  • combinaisons.xlsm
    10 KB · Affichages: 92
  • combinaisons.xlsm
    10 KB · Affichages: 101
Dernière édition:

ROGER2327

XLDnaute Barbatruc
Re : combinaisons devant donner un total

Bonjour gosselien.


Un essai en pièce jointe.
C'est du brut de fonderie qui aura vraisemblablement besoin d'un peu d'usinage, mais voyez d'abord si ça va dans le bon sens...​


Bonne journée.


ℝOGER2327
#7729


Dimanche 8 Gueules 142 (Fête de la Chandelle Verte - fête Suprême Tierce)
14 Pluviôse An CCXXIII, 1,5942h - avelinier
2015-W06-1T03:49:34Z
 

Pièces jointes

  • Somme prédite à termes fixés.xlsm
    20.3 KB · Affichages: 107
Dernière édition:

gosselien

XLDnaute Barbatruc
Re : combinaisons devant donner un total

Bonjour le forum, Roger2327,

je vais tester ça, et surtout essayer de comprendre le code, ce qui n'est pas gagné..
Est-il possible de commenter le code s'il fonctionne ? ce dont je me doute pas :)

P.
 

job75

XLDnaute Barbatruc
Re : combinaisons devant donner un total

Bonjour gosselien, Roger,

On peut utiliser cette fonction VBA matricielle qui fait des tirages aléatoires :

Code:
Function Recolle(v As Range, facture As Range)
Application.Volatile
If facture.Count = 1 Then Recolle = IIf(v = facture, "x", ""): Exit Function
Dim imax&, f, u&, a$(), cible#, n&, s#, i&
imax = 100000 'nombre maximum d'itérations, à adapter
f = facture 'matrice, plus rapide
u = UBound(f)
ReDim a(1 To u, 1 To 1)
cible = v
Randomize
Do
  n = n + 1
  If n > imax Then End
  s = 0
  For i = 1 To u
    a(i, 1) = ""
    If Rnd > 0.5 Then a(i, 1) = "x": s = s + f(i, 1)
  Next
Loop Until s = cible
Recolle = a 'vecteur vertical
End Function
Fichier joint.

A+
 

Pièces jointes

  • combinaisons(1).xls
    47 KB · Affichages: 94
  • combinaisons(1).xls
    47 KB · Affichages: 103
  • combinaisons(1).xls
    47 KB · Affichages: 89
Dernière édition:

gosselien

XLDnaute Barbatruc
Re : combinaisons devant donner un total

Bonjour Job75, Roger 2327 et le forum

@Job:ça montre une possibilité visible à la fois mais il serait plus facile de les avoir toutes à la droite l'une de l'autre, j'imagine donc par macro
@Roger: j'ai testé avec des chiffres avec décimales et là, ça ne fonctionne pas...

Merci de vos efforts et du partage :)
 

ROGER2327

XLDnaute Barbatruc
Re : combinaisons devant donner un total

Re...


(...=
je vais tester ça, et surtout essayer de comprendre le code, ce qui n'est pas gagné..
Est-il possible de commenter le code s'il fonctionne ? (...)
C'est possible. Je ne commente pas systématiquement 1.) parce que c'est long, et surtout 2.) parce que beaucoup de demandeurs se foutent complètement des réponses apportées, même lorsqu'elles ont demandées un vrai travail. Mais si votre intérêt est réel, vous aurez toutes les explications nécessaires.​
(...)
@Roger: j'ai testé avec des chiffres avec décimales et là, ça ne fonctionne pas...
(...)
Oui, ça ne fonctionne pas. Je m'en suis tenu aux données de votre demandes (données arrondies à l'entier).
Si vous abandonnez ce point de vue, remplacez la ligne​
Code:
Dim tDat, oDat(), UBoDat&, oPlg As Range, i&, j&, k&, s&, som
par​
Code:
Dim tDat, oDat(), UBoDat&, oPlg As Range, i&, j&, k&, s#, som#
Comme je vous l'ai dit plus haut
C'est du brut de fonderie qui aura vraisemblablement besoin d'un peu d'usinage, mais voyez d'abord si ça va dans le bon sens... (...)
Puisque la proposition semble aller dans le bon sens, et pour perdre le minimum de temps, il serait intéressant que vous posassiez entièrement votre véritable problème.
  • S'agit-il de traiter dix lignes ou dix mille ?
  • Peut-il y avoir des lignes vides intercalées dans la colonne Montant ?
  • Quid des éventuels doublons dans les données ?
  • Veut-on un relevé exhaustif des possibilités ou un échantillonnage ? Dans la seconde hypothèse, quelle est la taille de l'échantillon ? Quelles contraintes doit-on respecter ?
  • La présentation du résultat est-il imposé, ou peut-on en imaginer une autre ?
  • Bref, quelles sont toutes les contraintes du problèmes réel ?
Selon les réponses apportées à ces questions, les solutions peuvent (et, certainement, doivent) être très-différentes.


À vous lire.


ℝOGER2327
#7730


Dimanche 8 Gueules 142 (Fête de la Chandelle Verte - fête Suprême Tierce)
14 Pluviôse An CCXXIII, 5,3091h - avelinier
2015-W06-1T12:44:31Z
 

gosselien

XLDnaute Barbatruc
Re : combinaisons devant donner un total

Salut Patrick©
voir là :
Ce lien n'existe plus
et là :
;) :rolleyes: :cool:
Ce lien n'existe plus
:):D
Pat

Merci pour ce rappel Modeste !

je savais que j'avais eu ça entre les mains il y a des années mais pas moyen de mettre la main dessus (à cause du nom de fichier probablement), il s'agissait de la réponse d'un maitre en excel de l'époque: Tom Ogilvy (MPEP), et c'est aussi pour ça que je savais ne pas être capable de le refaire encore à l'heure actuelle..A la relire, je pense qu'il y a mieux , déjà en voyant la réponse de Roger2327 plus claire.


@Roger: un grand merci néanmoins pour ta réponse; ce que je peux dire:

je sais que c'est pour peu de lignes, (rapprochements de 10-15 factures par jour) mais il faudrait Toutes les possibilités oui.
La personne encode le total dans une cellule ici en "O1" et les montants reçus de la compta via SAP dans la colonne "E" et bien sûr les montants comportent des décimales. Il n'y a pas de lignes vides dans la colonne Montant et tout est libre vers la droite.
La présentation doit être l'actuelle de mon exemple reçu, légère contraite j'imagine
Je vais voir en modifiant comme tu me l'as indiqué déjà.
Perso, je ne me fiche pas (jamais) des réponses, elles sont TOUJOURS là pour apprendre, j'ai déjà bien appris en revenant sur un forum excel que j'avais quitté il y a des années sans plus faire de travaux sur excel; le commentaire sert pour plus tard en cas de relecture, j'essaye de le faire dans propres (petits) codes :D

Pour conclure: c'est PARFAIT comme c'est fait actuellement en changeant la ligne de déclaration des variables
Merci beaucoup !!!

Patrick
 
Dernière édition:

eriiic

XLDnaute Barbatruc
Re : combinaisons devant donner un total

Bonjour,

une proposition.
Optimisé mais comme c'est exponentiel si tu as 150 factures faut patienter...
eric
 

Pièces jointes

  • Accès Factures avec Somme Totale v4.3.2.xls
    137 KB · Affichages: 148
  • Accès Factures avec Somme Totale v4.3.2.xls
    137 KB · Affichages: 102

ROGER2327

XLDnaute Barbatruc
Re : combinaisons devant donner un total [RESOLU]

Suite...


Code commenté :​
Code:
Sub toto()
Dim oDat(), UBoDat&, oPlg As Range, i&, j&, k&, s#, som#, x
   Application.ScreenUpdating = False
'__________________________________________________________________________________________
'Récupération des données.
'  som         Somme à atteindre.
'  oDat()      Récupère les données dans la colonne "Montant".
'  UBoDat      Nombre de lignes jusqu'à la dernière cellule non vide de la colonne "Montant".
'  k           Compteur de colonnes de oDat
'  Data        Plage nommée : voir le "Gestionnaire de noms" pour voir sa définition.

   som = [O1].Value
   With [Data]
      Set oPlg = Range(.Cells(1, 1), .Offset(.Rows.Count, 0).End(xlUp)).Offset(1, 0)
      With oPlg.Resize(oPlg.Rows.Count + (oPlg.Rows.Count > 1), 2)
         oDat = .Value
         .Resize([Data].Rows.Count - 1, [Data].Columns.Count).ClearContents
      End With
      UBoDat = UBound(oDat, 1)
      k = 1: ReDim Preserve oDat(1 To UBoDat, 1 To k)
'__________________________________________________________________________________________
'Traitement des données.
'La méthode est bestiale : on va examiner les données une par une, puis les grouper deux par deux,
'trois par trois, etc., soit 2^UBoDat-1 possibilités, indexées par le compteur i.

      For i = 1 To 2 ^ UBoDat - 1
'__________________________________________________________________________________________
'  s     initialisé à zéro, va cumuler les données. Pour i=1, s prendra la première donnée,
'pour i=2, la deuxième, pour i=3, la première et la deuxième, pour i=4, la troisième, pour i=5,
'la première et la troisième, pour i=6, la deuxième et la troisième, pour i= 7, la première,
'la deuxième et la troisième, pour i=8, la quatrième, pour i=9, la première et la quatrième, etc.
'Pour i=64, la septième, pour i=65, la première et la septième, ...
'Pour i=2^x, la x+1ième, pour i=2^x+1, la première et la x+1ième, ...
'Pour i=UBoDat-1, la somme de toute les données.

         s = 0: For j = 1 To UBoDat: s = s + oDat(j, 1) * ((i \ 2 ^ (j - 1)) Mod 2): Next
'__________________________________________________________________________________________
'Si s est égal à la somme cherchée, on ajoute une colonne au tableau oDat, est on marque
'd'un"x" dans la dernière colonne tout les termes constitutifs de s.

         If s = som Then
            k = k + 1: ReDim Preserve oDat(1 To UBoDat, 1 To k)
            For j = 1 To UBoDat
               If (i \ 2 ^ (j - 1)) Mod 2 Then oDat(j, UBound(oDat, 2)) = "x"
            Next
         End If
      Next
'__________________________________________________________________________________________
'Restitution du résultat.

      .Offset(1).Resize(UBoDat, k).Value = oDat
   End With
   Application.ScreenUpdating = True
End Sub

Le nombre de groupement par un par un, deux par deux, trois par trois, ..., n-1 par n-1, n par n de n données est égal à 2[SUP]n[/SUP]-1, quoi qu'on en dise ici ou là.
Donc, compte tenu de la méthode bestiale utilisée ici, le temps de traitement double pour chaque donnée supplémentaire. Il y a certainement matière à optimisation !

Avec 20 données, il faut 7 à 8 s.
Avec 26 données, de l'ordre de 8 à 9 min.
Je n'ai pas cherché plus loin.​


Bonne soirée.


ℝOGER2327
#7731


Dimanche 8 Gueules 142 (Fête de la Chandelle Verte - fête Suprême Tierce)
14 Pluviôse An CCXXIII, 6,7977h - avelinier
2015-W06-1T16:18:52Z
 

Pièces jointes

  • Somme prédite à termes fixés (2c).xlsm
    54.9 KB · Affichages: 82

job75

XLDnaute Barbatruc
Re : combinaisons devant donner un total [RESOLU]

Le nombre de groupement par un par un, deux par deux, trois par trois, ..., n-1 par n-1, n par n de n données est égal à 2[SUP]n[/SUP]-1, quoi qu'on en dise ici ou là.

Effectivement, je me suis trompé en parlant de FACT(n).

Ma fonction posera donc problème à partir de n = 17 (ou n = 20 avec 1000000 d'itérations).

A+
 

ROGER2327

XLDnaute Barbatruc
Re : combinaisons devant donner un total [RESOLU]

Suite...


... légèrement optimisé, le code s'exécute en moins d'une demi-seconde pour vingt données, et en vingt-cinq secondes pour vingt-six données.​


Bonne nuit.


ℝOGER2327
#7732


Dimanche 8 Gueules 142 (Fête de la Chandelle Verte - fête Suprême Tierce)
14 Pluviôse An CCXXIII, 9,8494h - avelinier
2015-W06-1T23:38:19Z
 

Pièces jointes

  • Somme prédite à termes fixés (3).xlsm
    61.1 KB · Affichages: 100
Dernière édition: