IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

WinDev Discussion :

Casse tête infernal [WD16]


Sujet :

WinDev

  1. #1
    Membre émérite
    Femme Profil pro
    .
    Inscrit en
    Janvier 2012
    Messages
    996
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Gironde (Aquitaine)

    Informations professionnelles :
    Activité : .
    Secteur : Tourisme - Loisirs

    Informations forums :
    Inscription : Janvier 2012
    Messages : 996
    Points : 2 514
    Points
    2 514
    Par défaut Casse tête infernal
    Salut à tous,

    Je n'ai pas pour habitude de demander de l'aide, mais là, je sèche.

    Soit 16 montants (des factures par exemple)

    L'utilisateur donne un montant global (1150 euros, par exemple)

    Il s'agit de rechercher toutes les combinaisons possibles des 16 montants pré-cités qui pourrait aboutir au montant global.

    J'ai bien écrit un algo qui tente de faire cela, mais jusqu'à 8 factures ça passe, au delà, il lui faut parfois jusqu'à plusieurs heures.
    Le résultat est là mais bon...

    Comment les pointures qui sévissent ici, traiteraient cela de façon optimale ?

  2. #2
    Membre expérimenté
    Profil pro
    Inscrit en
    Avril 2010
    Messages
    913
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2010
    Messages : 913
    Points : 1 495
    Points
    1 495
    Par défaut
    Bonsoir
    Il me semble avoir vu un exemple qui traite ce cas.
    Voir la LST63:

    RAPPROCHEMENT : (WINDEV, WEBDEV, WINDEV Mobile)
    Recherche automatique des opérations à rapprocher (notes de frais, relevés bancaires...)


    L’exemple “WD Note de frais” est un exemple de programmation
    récursive permettant de proposer automatiquement à l’utilisateur les combinaisons possibles lors du remboursement d’une note de frais.
    En effet, lors d’un remboursement “global” d’une note de frais, il est utile de retrouver les tickets correspondants.
    L’exemple “WD Note de frais” effectue donc une recherche des combinaisons possibles entre :
    • Un montant de remboursement
    • Une liste de dépenses correspondant aux tickets
    L’exemple affiche alors la ou les combinaisons de tickets correspondant au montant.

  3. #3
    Membre expérimenté
    Profil pro
    Inscrit en
    Avril 2010
    Messages
    913
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2010
    Messages : 913
    Points : 1 495
    Points
    1 495
    Par défaut
    Une idee:
    Une requete qui renvoie les factures dont le montant est inferieur au total, triee par montant.
    Une procedure qui lit la requete et cherche les sommes de factures qui donne le resultat.

    programmation récursive
    Quelqu'un a une idee ou possede la LST 63 pour nous aider ?

  4. #4
    Membre confirmé
    Profil pro
    Inscrit en
    Février 2008
    Messages
    217
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2008
    Messages : 217
    Points : 487
    Points
    487
    Par défaut
    Bonjour,

    J'ai bien écrit un algo qui tente de faire cela, mais jusqu'à 8 factures ça passe, au delà, il lui faut parfois jusqu'à plusieurs heures.
    Bizarre car même avec un algo non optimisé, en testant toutes les possibilités il n'y a que 65535 possibilités (~2^16).
    Ça devrait être instantané.

    Cordialement

    Madsl@nD

  5. #5
    Membre chevronné
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Mars 2009
    Messages
    1 278
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Mars 2009
    Messages : 1 278
    Points : 2 151
    Points
    2 151
    Par défaut
    Bonjour,

    j'adore ce genre de casse tête !

    J'ai commencé un algo mais je bloque un peu... pas si évident que ça de trouver toutes les combinaisons !

    Concernant le nombre de possibilité je ne pense pas qu'il soit de 2^16 mais bien plus important ! d'autant plus si on accepte les prix avec une décimale...

    Pour faciliter les tests j'ai ajouté une notion de précision (qui définira l'unité) pour pouvoir tester avec un précision de 10 (donc des prix en dizaine) qui présente moins de possibilité... donc plus rapide !

    Tout ça pour dire je regarderais bien ton algo.... le mien n'est pas OP !
    SQL : le véritable Esperanto

    "Les patates à ta tata épatent ton tonton mais les pates aux thons à ton tonton épatent pas ta tata." (Michel Souris)

    MERCI DE NE PAS M'ENVOYER DE MESSAGE PRIVE POUR DES QUESTIONS TECHNIQUES SANS MON ACCORD !

  6. #6
    Membre confirmé
    Profil pro
    Inscrit en
    Février 2008
    Messages
    217
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2008
    Messages : 217
    Points : 487
    Points
    487
    Par défaut
    Voici un algo de test avec juste une optimisation. (suppression des montants supérieurs au montant à atteindre)
    Il y a peut être des erreurs, c'est tout frais.
    Sur mon poste, celui de 16 montants se fait en moins de 100ms, celui de 20 se fait en mois de 700ms.
    Par contre, sur beaucoup plus de montants je ne pense pas que ce soit un algo adapté car il y a surement moyen de diminuer énormément le nombre de solutions à tester.
    Chaque nouveau montant amène une puissance de 2 de solutions à tester en plus. Donc 30 montants et déjà plus d'un milliard de combinaisons.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    
    trMontant est un tableau de 16 réel = [16,12,30,60,120,200,500,900,550,10,56,489,321,456,789,548]
    //trMontant est un tableau de 20 reel = [16,12,30,60,120,200,500,900,550,10,56,489,321,456,789,548,94,36,15,580]
    tnSolutionPossible est un tableau d'entier
    rMontantAtteindre est un réel = 560
    rMontantSolution est un réel
    sUneSolution est une chaîne
    nPuissanceMontant est un entier
    
    ChronoDébut(1)
    //Dans un premier temps on supprime tous les montants supérieurs au montant à atteindre
    //A chaque suppression une puissance de 2 en moins à tester
    POUR l_iMontant = TableauOccurrence(trMontant) _A_ 1 PAS -1
    	SI trMontant[l_iMontant]>rMontantAtteindre ALORS
    		TableauSupprime(trMontant,l_iMontant)
    	FIN
    FIN
    
    //On tri le tableau par ordre décroissant pour sortir de la boucle le plus tot possible
    TableauTrie(trMontant,ttDécroissant)
    
    //On calcule toutes les possibilités restantes
    POUR l_iSolution = 1 _A_ Puissance(2,TableauOccurrence(trMontant))
    	rMontantSolution = 0
    	//Calcul de la solution
    	POUR l_iMontant = 1 _A_ TableauOccurrence(trMontant)
    		nPuissanceMontant = Puissance(2,l_iMontant-1)
    		rMontantSolution+=trMontant[l_iMontant]*(l_iSolution & nPuissanceMontant=nPuissanceMontant)
    		SI rMontantSolution>rMontantAtteindre ALORS
    			//On sort pour éviter des calculs inutiles, cette solution est impossible
    			SORTIR
    		FIN
    	FIN
    	//Montant OK ?
    	SI rMontantSolution = rMontantAtteindre ALORS
    		//On stocke la solution
    		TableauAjoute(tnSolutionPossible,l_iSolution)
    	FIN
    FIN
    
    //Affichage des possibilités
    POUR l_iSolution = 1 _A_ TableauOccurrence(tnSolutionPossible)
    	sUneSolution = ""
    	POUR l_iMontant = 1 _A_ TableauOccurrence(trMontant)
    		nPuissanceMontant = Puissance(2,l_iMontant-1)
    		SI tnSolutionPossible[l_iSolution] & nPuissanceMontant=nPuissanceMontant ALORS
    			sUneSolution+=[TAB]+trMontant[l_iMontant]
    		FIN
    	FIN
    	Trace(sUneSolution)
    FIN
    
    Info("Terminé en "+Val(ChronoFin(1))+" ms")
    Cordialement

    Madsl@nD

  7. #7
    Membre chevronné
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Mars 2009
    Messages
    1 278
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Mars 2009
    Messages : 1 278
    Points : 2 151
    Points
    2 151
    Par défaut
    Je pense qu'il ne faut pas de montants prédéfinis.... du moins c'est ce que je cherche à faire... mais peut être que je n'ai pas bien compris son objectif !
    SQL : le véritable Esperanto

    "Les patates à ta tata épatent ton tonton mais les pates aux thons à ton tonton épatent pas ta tata." (Michel Souris)

    MERCI DE NE PAS M'ENVOYER DE MESSAGE PRIVE POUR DES QUESTIONS TECHNIQUES SANS MON ACCORD !

  8. #8
    Membre confirmé
    Profil pro
    Inscrit en
    Février 2008
    Messages
    217
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2008
    Messages : 217
    Points : 487
    Points
    487
    Par défaut
    Citation Envoyé par michel.souris Voir le message
    Je pense qu'il ne faut pas de montants prédéfinis.... du moins c'est ce que je cherche à faire... mais peut être que je n'ai pas bien compris son objectif !
    Soit 16 montants (des factures par exemple)

    Je pense que des factures sont des montants "prédéfinis" ou alors je n'ai rien compris au but recherché.

  9. #9
    Membre chevronné
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Mars 2009
    Messages
    1 278
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Mars 2009
    Messages : 1 278
    Points : 2 151
    Points
    2 151
    Par défaut
    Ah ouais... t'as surement raison.... c'était putain de chaud de trouver l'ensemble des possibilités de montant !!!!! mais si c'est juste les combinaisons ça simplifie la donne
    SQL : le véritable Esperanto

    "Les patates à ta tata épatent ton tonton mais les pates aux thons à ton tonton épatent pas ta tata." (Michel Souris)

    MERCI DE NE PAS M'ENVOYER DE MESSAGE PRIVE POUR DES QUESTIONS TECHNIQUES SANS MON ACCORD !

  10. #10
    Membre émérite
    Femme Profil pro
    .
    Inscrit en
    Janvier 2012
    Messages
    996
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Gironde (Aquitaine)

    Informations professionnelles :
    Activité : .
    Secteur : Tourisme - Loisirs

    Informations forums :
    Inscription : Janvier 2012
    Messages : 996
    Points : 2 514
    Points
    2 514
    Par défaut
    Salut à vous tous,
    Je me disais bien que ça allait en exiter quelques-un.
    D'autant que ça peut être très utile.

    Mon algo n'est plus vraiment le mien, je tournais en rond alors
    je me suis basé sur l'exemple cité par Yusep :
    LST 63 : “WD Note de frais”.

    Sauf que je part d'une table mémoire avec les montants des factures,
    plutôt que des dits montants en fichier (ce qui ne change pas grand chose).

    Madsland a raison ça fait bien 65536 possibiltés.
    Mais ça monte bien entendu très vite : plus d'un million pour 20 factures.
    Bien sûr, j'élimine d'entrée les factures dont le montant est supérieur au montant global demandé.
    Oui, Michel il faut des montants avec décimales (2), mais ça ne multiplie pas le nombre de possibilités, un montant étant un montant avec ou sans virgule.
    Je ne cherche pas vraiment à le rendre fonctionnel pour 100 factures, ce serait un peu stupide, et de toutes façon inutilisable.
    Mais 32 factures, me semble une limite raisonnable, sauf que pour le moment c'est 30 minutes et mes Clients ne sont pas tous accros au café et à la clop.

    Il y a déjà une première chose que j'aimerais savoir faire (sans que ça prennent des heures) c'est lister en table mémoire toutes les possibilités.
    Et là je sèche, car comme le dit Michel :
    "pas si évident que ça de trouver toutes les combinaisons !"
    Car une fois la chose réalisée, après c'est fastoche.

    Comme je suis têtu, je persévère, mais c'est bien la premère fois qu'un truc me résiste aussi longtemps.
    Alors peut-être qu'à plusieurs ...

  11. #11
    Membre confirmé
    Profil pro
    Inscrit en
    Février 2008
    Messages
    217
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2008
    Messages : 217
    Points : 487
    Points
    487
    Par défaut
    Je viens de tester l'algo de la LST 63.
    J'ai testé le tableau de 20 réels avec les mêmes valeurs que dans mon exemple.
    Je n'ai compté que la recherche des solutions dans le chrono (pas d'affichage, pas d'initialisation des tableaux etc...).
    Verdict 101 secondes, je préfère mes 700ms

  12. #12
    Membre émérite
    Femme Profil pro
    .
    Inscrit en
    Janvier 2012
    Messages
    996
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Gironde (Aquitaine)

    Informations professionnelles :
    Activité : .
    Secteur : Tourisme - Loisirs

    Informations forums :
    Inscription : Janvier 2012
    Messages : 996
    Points : 2 514
    Points
    2 514
    Par défaut
    Madsland, je te tire mon chapeau.
    Surtout en tenant compte du temps que tu as mis à trouver une solution.

    Pour 20 factures, ce qui n'était pas jouable avant, devient très raisonnable
    avec ta solution.
    Par contre, 32 factures, il faut que j'oublie.
    J'essaye maintenant avec des monétaires, car c'est le but.

  13. #13
    Membre confirmé
    Profil pro
    Inscrit en
    Février 2008
    Messages
    217
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2008
    Messages : 217
    Points : 487
    Points
    487
    Par défaut
    En partant de mon algo, je pense qu'on peut encore diminuer le nombre de solution à tester. (exemple, la somme des 2 plus grand dépasse déjà le montant à atteindre)
    On peut aussi augmenter la rapidité en faisant ce traitement dans une DLL.
    Sinon il faut se baser sur un autre algo car je suis presque sur qu'il y a des solutions beaucoup plus simples pour arriver au résultat.

  14. #14
    Membre émérite
    Femme Profil pro
    .
    Inscrit en
    Janvier 2012
    Messages
    996
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Gironde (Aquitaine)

    Informations professionnelles :
    Activité : .
    Secteur : Tourisme - Loisirs

    Informations forums :
    Inscription : Janvier 2012
    Messages : 996
    Points : 2 514
    Points
    2 514
    Par défaut
    salut Madsland,

    - avec des monétaires ça ne marche pas.
    il affiche des tonnes de solutions dont certaines avec des 0.

    J'avoue ne pas bien comprendre.
    Il faut dire que je fatigue, puis-je abuser de ta patiente et de ta compétence ?

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
     
    trMontant est un tableau de 20 monétaires
    rMontantAtteindre est un monétaire = TXT_MONTANT //Montant recherché
    rMontantSolution est un monétaire
    i est un entier
    //La table ou je met les montants (limité à 20 pour le moment)
    POUR i=1 A 20 //Table_NotesDeFrais..Occurrence
    	TableSelectPlus(Table_NotesDeFrais,i)
    	SI MontantNote <= TXT_MONTANT ALORS
    		trMontant[i]=MontantNote
    	FIN
    FIN
     
    //trMontant est un tableau de 20 réel = [16,12,30,60,120,200,500,900,550,10,56,489,321,456,789,548+17,13,31,61]
     
    tnSolutionPossible est un tableau d'entier
    //rMontantAtteindre est un réel = 560
    //rMontantSolution est un réel
    sUneSolution est une chaîne
    nPuissanceMontant est un entier
     
    ChronoDébut(1)
    //Dans un premier temps on supprime tous les montants supérieurs au montant à atteindre
    //A chaque suppression une puissance de 2 en moins à tester
    POUR l_iMontant = TableauOccurrence(trMontant) _A_ 1 PAS -1
    	SI trMontant[l_iMontant]>rMontantAtteindre ALORS
    		TableauSupprime(trMontant,l_iMontant)
    	FIN
    FIN
    Message("Fin 1")
    //On tri le tableau par ordre décroissant pour sortir de la boucle le plus tot possible
    TableauTrie(trMontant,ttDécroissant)
     
    //On calcule toutes les possibilités restantes
    POUR l_iSolution = 1 _A_ Puissance(2,TableauOccurrence(trMontant))
    	rMontantSolution = 0
    	//Calcul de la solution
    	POUR l_iMontant = 1 _A_ TableauOccurrence(trMontant)
    		nPuissanceMontant = Puissance(2,l_iMontant-1)
    		rMontantSolution+=trMontant[l_iMontant]*(l_iSolution & nPuissanceMontant=nPuissanceMontant)
    		SI rMontantSolution>rMontantAtteindre ALORS
    			//On sort pour éviter des calculs inutiles, cette solution est impossible
    			SORTIR
    		FIN
    	FIN
    	//Montant OK ?
    	SI rMontantSolution = rMontantAtteindre ALORS
    		//On stocke la solution
    		TableauAjoute(tnSolutionPossible,l_iSolution)
    	FIN
    	Message(l_iSolution) //pour suivre l'avancement
    FIN
     
    //Affichage des possibilités
    MaSolution est une chaîne
    POUR l_iSolution = 1 _A_ TableauOccurrence(tnSolutionPossible)
    	sUneSolution = ""
    	POUR l_iMontant = 1 _A_ TableauOccurrence(trMontant)
    		nPuissanceMontant = Puissance(2,l_iMontant-1)
    		SI tnSolutionPossible[l_iSolution] & nPuissanceMontant=nPuissanceMontant ALORS
    			SI trMontant[l_iMontant]>0 sUneSolution+="+"+trMontant[l_iMontant] //test ajouté pour enlever les zéros
    		FIN
    	FIN
    	Info(sUneSolution)
    	MaSolution=MaSolution+RC+sUneSolution
    FIN
    Info(MaSolution)
    Info("Terminé en "+Val(ChronoFin(1))+" ms")

  15. #15
    Membre confirmé
    Profil pro
    Inscrit en
    Février 2008
    Messages
    217
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2008
    Messages : 217
    Points : 487
    Points
    487
    Par défaut
    J'ai remplacé les rééls par des monétaires et mis à part que le traitement est 3 fois plus long, j'ai les mêmes résultats.

    Avez-vous regardé les valeurs présentent dans trMontant après votre chargement ? (ligne 12)
    Je pense que le problème vient de là, vous devez avoir des montants = 0 et un montant = 0 entraine forcément beaucoup de solutions en plus possibles.

  16. #16
    Membre émérite
    Femme Profil pro
    .
    Inscrit en
    Janvier 2012
    Messages
    996
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Gironde (Aquitaine)

    Informations professionnelles :
    Activité : .
    Secteur : Tourisme - Loisirs

    Informations forums :
    Inscription : Janvier 2012
    Messages : 996
    Points : 2 514
    Points
    2 514
    Par défaut
    Désolé, Madsland,
    effectivement, comme le tableau est fixe,
    si le montant est supérieur à la valeur recherchée,
    dans le tableau on a des zéros.

    Fatigue+bêtise ne font pas bon ménage.

    En tout cas un grand merci et encore chapeau !

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. [Tableaux] Casse têtes de boucles
    Par Anduriel dans le forum Langage
    Réponses: 5
    Dernier message: 28/06/2006, 01h24
  2. Casse tête chinois
    Par Jahjouh dans le forum Algorithmes et structures de données
    Réponses: 3
    Dernier message: 15/03/2006, 10h04
  3. requête SQL un peu casse tête
    Par hellbilly dans le forum Langage SQL
    Réponses: 4
    Dernier message: 15/12/2005, 11h03
  4. Classe, pile, pointeurs et casse-tête!
    Par zazaraignée dans le forum Langage
    Réponses: 6
    Dernier message: 26/09/2005, 17h57
  5. casse-tête excel
    Par gregius dans le forum Access
    Réponses: 2
    Dernier message: 21/09/2005, 17h38

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo