ALGO pour les bons

Signaler
Messages postés
17
Date d'inscription
jeudi 19 octobre 2000
Statut
Membre
Dernière intervention
23 août 2005
-
Messages postés
110
Date d'inscription
jeudi 9 mai 2002
Statut
Membre
Dernière intervention
11 mars 2010
-
voila mon probleme. j'ai un tableau (environ 400 elements ayant toutes un prix), j'ai un montant. je voudrais trouver la somme des prix qui se rapproche le plus du montant
exemple : j'ai 400f
piece1:100
piece2:50
piece3:20
piece4:200
piece5:320

donc la il faudrai que je prenne les pieces 2,3,5
ce qui va tombe a 390

il faut sans doute que je classe mes pieces.
j'ai trouver un algo mais il me fait si j'ai 400 pieces 400! posibilitées ce qui fait un peu beaucoup.
voila ,merci de votre aide.

8 réponses

Messages postés
1471
Date d'inscription
mardi 5 février 2002
Statut
Membre
Dernière intervention
20 octobre 2014
12
algo grossier :

trier le tableau selon les prix

prendre le max <400 (le 320)

puis prendre le max <80 (400-320) cad 50

.....

reste 10
0
Messages postés
110
Date d'inscription
jeudi 9 mai 2002
Statut
Membre
Dernière intervention
11 mars 2010
1
Trie ton tableau avec un agorithme de trie et non pas avec une boucle for de niveau 1...

Par la suite, si tu comprends les algo de trie, tu vas être capable de l'adapter pour trouve la valeur la plus pres !
0
Messages postés
235
Date d'inscription
mercredi 4 avril 2001
Statut
Membre
Dernière intervention
9 novembre 2007

lol charlie, j'attends un exemple pour voir, pcq là, que de la gueule de non-connaisseur :)
0
Messages postés
110
Date d'inscription
jeudi 9 mai 2002
Statut
Membre
Dernière intervention
11 mars 2010
1
Allo...

Laisse moi 1 jour ou 2...
J'ai vu ca dans mes cours de C++.

Y'a moyen de trier des tableaux d'une manière plus performante qu'une boucle for! Je vais l'essayé mais le principe de base est de séparer le tableau en petit bloc et le trier ainsi. Ca permet d'avoir un nombre de possibilité inférieur au nombre total d'élément. Mais le hic avec le VB, c'est que ca utilise la récursivité. Et en VB, c'est pas bien bien sont fort! Alors, je vais vérifier ca en fin de semaine!!!
0
Messages postés
235
Date d'inscription
mercredi 4 avril 2001
Statut
Membre
Dernière intervention
9 novembre 2007

lol te casse pas la tête pour rien, c pas grave :)
0
Messages postés
110
Date d'inscription
jeudi 9 mai 2002
Statut
Membre
Dernière intervention
11 mars 2010
1
non non non... C'est pas compliqué a faire... Mais je viens de me rendre compte que comme mon code viens du C, il n'est pas compatible VB. VB n'est pas assez puissant en récursivité pour y parvenir... Mon algo fonctionne mais seulement avec les petits tableaux... un de 100 éléments par exemple... ca plante royalement!!! Reste qu'en C... c'est puissant!!! Par évident sur le coup mais super cool quand tu comprends le principe.

Voici mon algo!!!

1 form... 1 list et 2 boutons

Private Tableau(4) As Integer

Private Sub Command1_Click()

Dim i As Integer

Tableau(0) = 11
Tableau(1) = 7
Tableau(2) = 5
Tableau(3) = 2
Tableau(4) = 9

For i = 0 To 4
List1.AddItem Tableau(i), i
Next

End Sub

Private Sub Command2_Click()
QuickSort 0, 4

For i = 0 To 4
List1.RemoveItem (i)
List1.AddItem Tableau(i), i
Next

End Sub

Public Function QuickSort(inf As Integer, sup As Integer)

Dim milieu As Integer

If (sup > inf) Then ' s'il y a au moins 2 éléments
milieu = Partition(inf, sup)

'Trie la partie de gauche
QuickSort inf, milieu

'Trie la partie de droite
QuickSort milieu + 1, sup
End If

End Function

Public Function Partition(inf As Integer, sup As Integer) As Integer

Dim Pivot, Tempo
Dim i As Integer, j As Integer

Pivot = Tableau((sup + inf) / 2)
i = inf - 1
j = sup + 1

' tant que les index ne croisent pas

While (i < j)
'Conserver les éléments les plus petits ou égaux au pivot à gauche
Do
i = i + 1
Loop While (Tableau(i) < Pivot)

Do
j = j - 1
Loop While (Tableau(j) > Pivot)

'Permuter les éléments qui n esont pas à leur place

If (i < j) Then
Tempo = Tableau(i)
Tableau(i) = Tableau(j)
Tableau(j) = Tempo
End If
Wend

Partition = j

End Function

Voici un 2e Algo de trie que qq a mis sur le forum...

' Algorithme de tri "shell" sur un tableau Total(Maximum)
Dim i As Integer, j As Integer, k As Integer, l As Integer, Provi As même chose que Total
k = 1
While k <= Maximum
k = k * 2
Wend
Do
k = (k - 1) \ 2
If k = 0 Then Exit Do ' tri terminé
For l = 1 To Maximum - k
i = l
Do
j = i + k
If Total(i) > Total(j) Then Exit DoProvi Total(i): Total(i) Total(j): Total(j) = Provi
i = i - k
Loop While i > 0
Next l
Loop
0
Messages postés
235
Date d'inscription
mercredi 4 avril 2001
Statut
Membre
Dernière intervention
9 novembre 2007

ah ouais carrement..... bravo :)
en fait c kler que VB ne suit plus... lol

++
0
Messages postés
110
Date d'inscription
jeudi 9 mai 2002
Statut
Membre
Dernière intervention
11 mars 2010
1
mon ami m'a dit que le plus simple... tu te fait une liste bidon...

Tu copie tout dans la liste, tu te sert de ses options de trie et par la suite... tu rapatries tes données... Dans certains cas, ca peut etre pratique car les listes ont plusieurs mode de trie et peut-être des filtres en plus...

Mais mon code de C, on voit ca dans mon cours de Génie Électrique a l'université!
0