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