Casse tête infernal

Version imprimable

11/12/2013, 18h25
serendib

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 ?
11/12/2013, 19h42
Yusep

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...)

http://www.pcsoft.fr/lst/img/lst63/note-de-frais.jpgL’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.
11/12/2013, 20h20
Yusep

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.

Citation:

programmation récursive

Quelqu'un a une idee ou possede la LST 63 pour nous aider ?
12/12/2013, 08h16
madsland

Bonjour,

Citation:

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
12/12/2013, 09h48
michel.souris

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 !

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:

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

12/12/2013, 10h20
michel.souris

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 !
12/12/2013, 10h23
madsland

Citation:

Envoyé par michel.souris

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é.
12/12/2013, 10h32
michel.souris

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 :)
12/12/2013, 10h40
serendib

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 ...
12/12/2013, 10h44
madsland

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/2013, 11h30
serendib

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.
12/12/2013, 11h44
madsland

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.

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:

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")

12/12/2013, 12h48
madsland

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.
12/12/2013, 13h00
serendib

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 !