Citation :
À la main ça s'annonce casse pied mais je suis sur que y a moyen de bricoler un algo qui le fait pour moi ^^
C'est plus compliqué qu'il n'y paraît. A une époque j'avais tenté de réaliser un programme capable de déterminer l'arrangement optimal me permettant de minimiser les coûts moyennant un pool de cartes données et un pool de vendeurs donné (ainsi que leurs dispos, grille de frais de ports, montant de commande minimum). C'est un problème relativement similaire à celui que tu exposes
(1).
Je n'ai pas trouvé d'algorithme miraculeux donc je suis parti sur un bête bruteforce des arrangements de cartes possibles, et je me suis dit que je l'optimiserais en mode
backtracking.
Malheureusement la 1ère itération de mon algo (un simple algo de combinatoire sans vérification
a priori des contraintes de dispo) avait une complexité bien trop élevée et la résolution s'éternisait après seulement quelques cartes et quelques vendeurs. En gros il fonctionnait pour les pools de cartes que je pouvais traiter moi-même de tête quasiment à la même vitesse depuis l'achat de deck à un MVillois.
J'ai cherché à optimiser l'algorithme pour filtrer sur les arrangements valides (en tenant compte de la disponibilité des cartes de chaque vendeur
a priori), mais je me suis arrêté en cours de route parce que je n'avais plus le temps (et j'ai perdu la motivation par la suite). Un début de réflexion est
disponible ici (2).
Quoi qu'il en soit, MagicCardMarket a implémenté une version simplifiée de l'algorithme qui ne fonctionne pas trop mal (Acheter -> Mes wants lists => Achat automatique)
(3). Dommage que ce ne soit pas disponible sur MV ! Il faut dire que MCM a un avantage vu qu'ils ont en base de données la grille des frais de port pour chaque vendeur...
(1)
A vrai dire, ton problème est une version plus générale du problème qui tient également compte des arrangements incomplets, et qui exclut les arrangements dont le prix associé dépasse un certain seuil. Il y a également moyen de réduire les volumes de cartes au préalable en excluant d'emblée les arrangements impossibles évidents (carte unitairement trop chère chez le vendeur le moins cher, etc.), donc peut-être qu'une bruteforce a posteriori de cette simplification est plus réaliste si ton montant maxi est peu élevé.
(2)
Une fois un algo satisfaisant trouvé (satisfaisant = complexité pas exponentielle si possible...), il ne doit pas être impossible de l'optimiser en tronquant les branches de l'arbre qui sont sous-optimales par rapport au meilleur arrangement déjà trouvé jusque là, voire en tronquant les branches sans solution valide en tenant compte des critères de disponibilité plus étendus (montant de commande minimum par exemple).
Une autre approche pourrait être un algorithme par exclusion de vendeur. Tu prends une carte de ton pool, puis tu regardes la liste des arrangements de vendeurs ne proposant que cette carte (parmi ton pool) et qui ont la carte en quantité suffisante, puis tu exclues tous les vendeurs sauf ceux de l'arrangement le moins cher. Puis tu passes à la carte suivante. Une fois toutes les cartes traitées individuellement, tu recommences avec les arrangements de cartes plus complexes. Ça peut aussi être un moyen de filtrer la liste des vendeurs avant d'appliquer l'algorithme décrit précédemment.
Alternativement, ce genre de problème est un candidat sympathique pour un algorithme génétique, si ça tente quelqu'un !
(3)
Si j'ai bien compris, leur implémentation prend pas mal de raccourcis qui excluent d'emblée certaines combinaisons qui pourraient être valides, mais c'est compréhensible pour des raisons de performance. Cela-dit ils ont également enrichi leur outil avec pas mal de fonctionnalités intéressantes (filtre sur le pays d'origine du vendeur notamment, ou la possibilité, plus anecdotique, de minimiser le nombre de commandes au lieu du prix final). Il manque encore 2 ou 3 joyeusetés (prioriser les cartes en meilleur état, voire leur affecter un coefficient de prix différent en fonction de l'état) mais c'est plutôt intéressant.