Discussion :

[tromaltsec]

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

[univscien]

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.

[tromaltsec]

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).

[pseudocode]

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).

[tromaltsec]

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

[korte]

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"