Bonjour, je recherche la meilleure solution parmi un très grand nombre de possibilités.
Imaginons deux individus A et B. Ils participent chacun à 10 épreuves différentes (appelées e1 à e10) et chaque épreuve leur rapporte les points a1 à a10 et b1 à b10 respectivement.
On souhaite connaître leur meilleur total en prenant seulement 5 épreuves de chacun, mais on ne peut pas prendre 2 fois les points d'une épreuve (ex: on doit prendre pour e4 soit a4 soit b4, mais pas les deux).
Je parcours donc les possibilités (nombreuses !) comme suit:
s1=a1+a2+a3+a4+a5+b6+b7+b8+b9+b10
s2=a1+a2+a3+a4+b5+a6+b7+b8+b9+b10
s3=a1+a2+a3+a4+b5+b6+a7+b8+b9+b10
... et ainsi de suite.
Le hic c'est le nombre de possibilités (j'ai même pas calculé tellement ça me fait peur).
N'y a-t-il pas plus simple et plus rapide ? Une solution que je ne verrais pas ?
J'ai pensé à utiliser une méthode d'élagage genre alpha-beta, mais ça ne me semble pas très efficace...
Quelqu'un aurait-il une idée de génie ? :)
Merci de vos suggestions !
(Si mes explications n'ont pas été claires, je peux préciser...)
Forum Programmation.autre Algorithme optimum
11
août
2005
# Complexité
Posté par Antoine Schweitzer-Chaput . Évalué à 3.
Si mes souvenirs d'écoles sont encore bons, il doit y en avoir 252 (tu choisis 5 épreuves parmi 10 -> 252 combinaisons, que tu affectes à A et les autres vont à B -> aucun choix) ce qui est vraiment pas énorme.
# Une idée comme ca
Posté par Pascal Terjan (site web personnel) . Évalué à 3.
Calculer c1=a1-b1, c2=a2-b2, ...
Prendre les 5 epreuves avec les plus grandes valeurs de c et les compter pour a, compter les autres pour b.
[^] # Re: Une idée comme ca
Posté par charlieecho . Évalué à 1.
Ca marche et c'est rapide.
Effectivement, maximiser
(a1 ou b1) + (a2 ou b2) + ... + (a10 ou b10)
revient à maximiser
b1 + b2 + ... + (5 parmi {c1, c2, c3, ...})
Donc tant qu'à prendre 5 parmi les c, autant prendre les 5 plus grands.
# une autre idée
Posté par errno . Évalué à 2.
liste
tu vas obtenir quelque chose du genre :
a3 - b4 - a4 - b2 - b5 - a7 - b7 - b3 - a5 - ...
tu parcours cette liste et pour chaque note, tu récupère son indice puis tu
supprimes de la liste la note qui a le meme indice, dans notre exemple :
tu es sur a3, l'indice est donc 3
tu parcours la suite de la liste jusqu'a tombé sur b3 puis tu le supprime,
on a donc :
a3 - b4 - a4 - b2 - b5 - a7 - b7 - a5 - ...
tu recommence avec b4 pour obtenir :
a3 - b4 - b2 - b5 - a7 - b7 - a5 - ...
etc... jusqu'a la fin de la liste et tu auras le plus grand total.
en esperant avoir été + ou - clair
[^] # Re: une autre idée
Posté par errno . Évalué à 1.
[^] # Re: une autre idée
Posté par arnaudus . Évalué à 1.
T'es sûr que tu tombes sur le meilleur résultat possible? Imagine en réduisant à 4 épreuves (j'ai pas toute la journée :-) :
a b
9 8
6 3
7 8
7 2
Ton algo va te donner a1 b3 a4 b2 (soit 27), alors que choisir par exemple b1 b3 a2 a4 t'aurait donné 31! Donc c'est pas bon.
Il doit bien y avoir un moyen de ne pas explorer toutes les possibilités, mais finalement la complexité de la recherche intégrale est linéaire, donc je ne vois pas vraiment le problème.
[^] # Re: une autre idée
Posté par errno . Évalué à 1.
Mon algo donnera a1 b3 a4 a2 (soit 30)
et b1 b3 a2 a4 = 8 + 8 + 6 + 7 = 29
Cependant il est vrai que je n'avais pas compris qu'il fallait obligatoirement 5 de chaque.
Je vais me repencher sur le problème. :)
[^] # Re: une autre idée
Posté par arnaudus . Évalué à 1.
Disons que c'était ton algo modifié pour prendre en compte la partie du problème qui n'était pas considérée (tri, puis choix, avec élimination de tous les a quand 5 a avaient été choisis).
et b1 b3 a2 a4 = 8 + 8 + 6 + 7 = 29
C'est ma faute, idiot que je suis, j'ai cru que j'étais capable de faire ça sans calculette :-)
[^] # Re: une autre idée
Posté par arnaudus . Évalué à 2.
1) On fait une première passe pour déterminer qui de a ou de b est le plus fort (celui qui a gagné le plus d'épruves parmi les N épreuves). F est le fort, f le faible.
2) On sélectionne pour f toutes les épreuves gagnées par f. On en a donc déja X <= N/2
3) On sélectionne ensuite pour f, parmi les épreuves restantes, les N/2 - X meilleurs scores de f, sans regarder le score de F. On a alors la totalité des N/2 épreuves de f.
4) Il ne reste donc plus qu'à assigner les N/2 épreuves restantes à F.
Par contre, je ne sais pas si ça gère bien d'éventuelles égalités.
# Merci pour vos solutions
Posté par Alexandre Dombrat . Évalué à 1.
Concernant la complexité pas si grande pour un calcul exhaustif, il faut savoir que ce calcul minime pour une équipe, se fera sur une page web avec un plus grand nombre de concurrents. Du coup, je tenais à faire un calcul rapide, le chargement des données depuis la base postgres avec traitement pour affichage me prenant pas mal de temps déjà...
J'avais pensé à la solution de calculer les différences entre les deux membres de l'équipe, mais j'avais dû me planter, je pensais que j'oubliais des cas plus optimaux.
En tous cas, merci encore, je vais gagner un temps précieux avec ça... :)
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.