[Optimisation] Algorithme de réduction

Bonjour, j'espère tout d'abord être dans la bonne section. Mon problème se situe dans la conception d'un algorithme permettant de calculer la réduction maximale d'un panier d'articles selon un carnet de coupons de réduction.
Pour cela j'ai essayé de découper le but recherché en règles simples :

A savoir qu'un coupon ne peut être utilisé que pour un seul article.

Un coupon peut avoir soit une valeur fixe soit une valeur dépendant du prix de l'article.

Un article ne peut utiliser qu'un seul coupon.

La réduction la plus importante doit être effectuée

On doit consommer le moins de coupons possible pour atteindre la réduction la plus importante.


Le soucis c'est que je ne vois pas du tout comment faire pour gérer les cas particulier du genre
Article1 associé au coupon1 (10% de remise)

Article2 associé au coupon1 (10% de remise) coupon2 1,5 €

Si article1=10€ et article2<25€ alors remise maximale 2,5€ (2 coupons utilisés)
Si article1=10€ et article2=25€ alors remise maximale 2,5€ (1 coupon utilisé)
Si article1=10€ et article2>25€ alors remise maximale 10% de article2 (1 coupon utilisé)


L'exemple est simple car il ne met en jeu que 2 coupons sur 2 articles mais je ne vois pas comment pousser ce raisonnement pour x articles et y coupons.

Si quelqu'un avait une idée je suis preneur parce que pour le moment à part avoir exploser le mur de mon bureau à coups de tête et avoir une bonne migraine je ne vois pas comment commencer.

Merci d'avance

Tu peux tester toutes les combinaisons, c'est la méthode bourrin mais çà marche. Dans ce cas il te faut minimum autant de coupon que d'article (quitte à rajouter des 0€).
Soit X le nombre d'article et Y le nombre de coupon, alors il y a N = Y!/(Y-X)! possibilités.

Merci pour cette réponse mais le soucis c'est que de tester "à la bourrin" ça ne me convient pas vraiment car je dois utiliser un minimum de temps. Je suis sur que suivant la méthode employée il est possible de diminuer le nombre de tests et donc le temps (en gros c'est plus de l'optimisation que je cherche à faire).

Tu as essayé de faire une recherche avec les mots clés "système réducteur" sur ce forum ? ;)

Les problèmes de systèmes réducteurs sont généralement NP (sauf cas particulier). Donc à part tester toutes les solutions, tu ne peut pas être sûr d'avoir trouvé la "meilleure" solution.

Tu peux juste trouver des astuces pour stopper l'exploration de certaines branches pour lesquelles tu es 100% sûr de ne pas arriver a une meilleure solution (algo : branch & bound).

Merci pour cette réponse, je vais me pencher sur ces mots clés pour une recherche approfondie.

Première chose: tu manques de méthodes dans la description de ton problème. Il faut que tu décrives tes variables, ce que tu cherches à optimiser, tes éventuelles contraintes.

Deuxième chose: une fois que tu as formulé ton problème qualifie-le: les variables sont des entiers, des réels ou les deux , les contraintes sont linéaires ou quadratiques, etc. Et à partir de là cherchent des méthodes de résolution

Les mots clés concernant ton problème sont plutôt "optimisation combinatoire sans contraintes" et "programmation linéaire entière/binaire"

Quelques idées générales

1- si tu ne peux utiliser qu'un coupon par article, et si chaque coupon ne porte que sur un article, tu peux commencer par choisir, pour chaque article le "coupon idéal", en calculant la remise (en euros) de chaque coupon sur chaque article. Cette recherche est linéaire par raport au nombre de coupons, et va te donner une liste d'articles avec leur prix de départ et leur réduction optimale (qui coute un coupon à chaque fois)

2- après, tu te ramènes à un problème de sac à doc (knapsack, y'en a des kilos sur l'internet), le but étant de choisir un nombre minimal d'article, dans un budget donné, et en maximisant la remise. Ce problème est NP complet, mais l'ordre, maintenant est le nombre d'articles, pas le nombre de coupons. Du coupk, l'énumération marchera mieux.

3- si tu ne peux énumérer (trop d'articles) tu peux soit utiliser des algorithmes d'accélération (branch and bound, branch and cut), soit te lancer dans des algos approximatifs. On est dans une situation dans laquelle les algorithmes génétiques devraient faire des merveilles.

Mais bon, réduis d'abord ton problème en éliminant les coupons inutiles...

Francois

perso je pense pas que le problème soit dans NP et il peut être réduit à un problème d'optimisation sans contrainte. L'artillerie lourde du BB et autres algos génétique n'est peut être pas nécessaires car dans tous les cas le problème est approximable et des algorithmes polynomiaux peuvent être employés.

Citation:

---

Envoyé par korte

perso je pense pas que le problème soit dans NP et il peut être réduit à un problème d'optimisation sans contrainte. L'artillerie lourde du BB et autres algos génétique n'est peut être pas nécessaires car dans tous les cas le problème est approximable et des algorithmes polynomiaux peuvent être employés.

---

j'avoue que je ne sais pas trop. Tel que formulé dans le PO :

Citation:

---

On doit consommer le moins de coupons possible pour atteindre la réduction la plus importante.

---

je ne vois pas d'autre solution que de commencer par chercher la réduction la plus importante atteignable avec les articles/coupons dont on dispose. Et dans un deuxième temps de réduire le nombre de coupons nécessaires.