Bonjour.
Je suis à la recherche d'un algorithme WD pour réaliser le traitement
suivant:
En quelques mots, je dois trouver un algorithme permettant d'utiliser au
mieux des points de fidélité pour acheter des articles.
Voici l'explication du problème:
Le fichier ARTICLE contient des articles à vendre. Chaque article a un
en EURO, un prix en points de fidélité et un nombre de points de fidélité
octroyé à chaque unité vendue de cet article.
Lors de chaque vente, l'acheteur peut payer soit en EURO, soit en points
fidélité qu'il aura collectionné au cours de ses achats précédents.
Le problème est le suivant: Il faut optimiser le paiement en points de
fidélité. En d'autres mots, le logiciel doit spécifier dans la liste des
articles achetés par le client, lesquels il doit payer au moyen de ses
points de fidélité afin de les utiliser au mieux.
L'acheteur remet au vendeur tous ses points de fidélité. Le vendeur encode
dans le programme le nombre de points reçus.
Il faut à ce moment là que le logiciel, sur base des articles sélectionnés
par l'acheteur, optimise au mieux le paiement au moyen des points fidélité
remis, tout en sachant qu'un article ne peut être payé partiellement avec
des points de fidélité.
Exemple:
L'acheteur souhaite acheter les articles suivants:
Qtté Article Prix unitaire EUR Prix unitaire
points fidélité
3 A 2.50? 6pts
1 B 5? 15pts
5 C 0.6? 2pts
Le total de points fidélité nécessaire pour payer cet achat est de 43 (2x6
+1x15 + 5x2).
Imaginons que l'acheteur remette au vendeur 16 points de fidélité.
Question: Comment utiliser au mieux ces points pour payer cet achat?
Dans notre exemple, la meilleure utilisation est:
2xA + 2xC = 2x6 + 2x2 = 16 points, solde de points à utiliser = 0
J'ai déjà consulté les archives du forum et j'ai déjà trouvé la fonction
récursive de Fabrice qui fait cela en partie.
Néanmoins, je pense que ce problème est plus complexe car:
1. Il ne faut pas forcément arriver au nombre de points total à utiliser
mais sans approcher au plus, sans toutefois le dépasser. Ainsi, par
si l'acheteur remet 30 points au vendeur dans l'exemple cité, je pense que
l'on n'arrive pas à utiliser tous les points remis (30) mais qu'on arrive
mieux à 29 (1x15 + 2x6 + 1x2). Il faut dans ce cas que le logiciel me
l'utilisation optimale à faire des points tout en indiquant le solde de
points (1 dans ce cas) à rendre à l'acheteur.
2. LA quantité d'articles achetés est limité. On doit donc, à l'inverse du
problème de B. Neve, fixer des limites par article qui sont respectivement
les quantités des divers articles achetés par le client (dans notre
3A, 1B et 5C).
Après avoir bien analysé la fonction récursive de Fabrice, je n'arrive pas
trouver la solution.
Quelqu'un peut-il me donner un coup de pouce? Je cale...
Merci d'avance et Bonnes fêtes.
François
Bonjour.
Je suis à la recherche d'un algorithme WD pour réaliser le traitement
suivant:
En quelques mots, je dois trouver un algorithme permettant d'utiliser au
mieux des points de fidélité pour acheter des articles.
Voici l'explication du problème:
Le fichier ARTICLE contient des articles à vendre. Chaque article a un
en EURO, un prix en points de fidélité et un nombre de points de fidélité
octroyé à chaque unité vendue de cet article.
Lors de chaque vente, l'acheteur peut payer soit en EURO, soit en points
fidélité qu'il aura collectionné au cours de ses achats précédents.
Le problème est le suivant: Il faut optimiser le paiement en points de
fidélité. En d'autres mots, le logiciel doit spécifier dans la liste des
articles achetés par le client, lesquels il doit payer au moyen de ses
points de fidélité afin de les utiliser au mieux.
L'acheteur remet au vendeur tous ses points de fidélité. Le vendeur encode
dans le programme le nombre de points reçus.
Il faut à ce moment là que le logiciel, sur base des articles sélectionnés
par l'acheteur, optimise au mieux le paiement au moyen des points fidélité
remis, tout en sachant qu'un article ne peut être payé partiellement avec
des points de fidélité.
Exemple:
L'acheteur souhaite acheter les articles suivants:
Qtté Article Prix unitaire EUR Prix unitaire
points fidélité
3 A 2.50? 6pts
1 B 5? 15pts
5 C 0.6? 2pts
Le total de points fidélité nécessaire pour payer cet achat est de 43 (2x6
+1x15 + 5x2).
Imaginons que l'acheteur remette au vendeur 16 points de fidélité.
Question: Comment utiliser au mieux ces points pour payer cet achat?
Dans notre exemple, la meilleure utilisation est:
2xA + 2xC = 2x6 + 2x2 = 16 points, solde de points à utiliser = 0
J'ai déjà consulté les archives du forum et j'ai déjà trouvé la fonction
récursive de Fabrice qui fait cela en partie.
Néanmoins, je pense que ce problème est plus complexe car:
1. Il ne faut pas forcément arriver au nombre de points total à utiliser
mais sans approcher au plus, sans toutefois le dépasser. Ainsi, par
si l'acheteur remet 30 points au vendeur dans l'exemple cité, je pense que
l'on n'arrive pas à utiliser tous les points remis (30) mais qu'on arrive
mieux à 29 (1x15 + 2x6 + 1x2). Il faut dans ce cas que le logiciel me
l'utilisation optimale à faire des points tout en indiquant le solde de
points (1 dans ce cas) à rendre à l'acheteur.
2. LA quantité d'articles achetés est limité. On doit donc, à l'inverse du
problème de B. Neve, fixer des limites par article qui sont respectivement
les quantités des divers articles achetés par le client (dans notre
3A, 1B et 5C).
Après avoir bien analysé la fonction récursive de Fabrice, je n'arrive pas
trouver la solution.
Quelqu'un peut-il me donner un coup de pouce? Je cale...
Merci d'avance et Bonnes fêtes.
François
Bonjour.
Je suis à la recherche d'un algorithme WD pour réaliser le traitement
suivant:
En quelques mots, je dois trouver un algorithme permettant d'utiliser au
mieux des points de fidélité pour acheter des articles.
Voici l'explication du problème:
Le fichier ARTICLE contient des articles à vendre. Chaque article a un
en EURO, un prix en points de fidélité et un nombre de points de fidélité
octroyé à chaque unité vendue de cet article.
Lors de chaque vente, l'acheteur peut payer soit en EURO, soit en points
fidélité qu'il aura collectionné au cours de ses achats précédents.
Le problème est le suivant: Il faut optimiser le paiement en points de
fidélité. En d'autres mots, le logiciel doit spécifier dans la liste des
articles achetés par le client, lesquels il doit payer au moyen de ses
points de fidélité afin de les utiliser au mieux.
L'acheteur remet au vendeur tous ses points de fidélité. Le vendeur encode
dans le programme le nombre de points reçus.
Il faut à ce moment là que le logiciel, sur base des articles sélectionnés
par l'acheteur, optimise au mieux le paiement au moyen des points fidélité
remis, tout en sachant qu'un article ne peut être payé partiellement avec
des points de fidélité.
Exemple:
L'acheteur souhaite acheter les articles suivants:
Qtté Article Prix unitaire EUR Prix unitaire
points fidélité
3 A 2.50? 6pts
1 B 5? 15pts
5 C 0.6? 2pts
Le total de points fidélité nécessaire pour payer cet achat est de 43 (2x6
+1x15 + 5x2).
Imaginons que l'acheteur remette au vendeur 16 points de fidélité.
Question: Comment utiliser au mieux ces points pour payer cet achat?
Dans notre exemple, la meilleure utilisation est:
2xA + 2xC = 2x6 + 2x2 = 16 points, solde de points à utiliser = 0
J'ai déjà consulté les archives du forum et j'ai déjà trouvé la fonction
récursive de Fabrice qui fait cela en partie.
Néanmoins, je pense que ce problème est plus complexe car:
1. Il ne faut pas forcément arriver au nombre de points total à utiliser
mais sans approcher au plus, sans toutefois le dépasser. Ainsi, par
si l'acheteur remet 30 points au vendeur dans l'exemple cité, je pense que
l'on n'arrive pas à utiliser tous les points remis (30) mais qu'on arrive
mieux à 29 (1x15 + 2x6 + 1x2). Il faut dans ce cas que le logiciel me
l'utilisation optimale à faire des points tout en indiquant le solde de
points (1 dans ce cas) à rendre à l'acheteur.
2. LA quantité d'articles achetés est limité. On doit donc, à l'inverse du
problème de B. Neve, fixer des limites par article qui sont respectivement
les quantités des divers articles achetés par le client (dans notre
3A, 1B et 5C).
Après avoir bien analysé la fonction récursive de Fabrice, je n'arrive pas
trouver la solution.
Quelqu'un peut-il me donner un coup de pouce? Je cale...
Merci d'avance et Bonnes fêtes.
François
Cet algo fonctionne mais il y a, à mes yeux, deux problèmes:
1. Le nombre d'essais pour trouver la solution peut être élevé car, malgré
certains tests, le principe est de tester TOUTES les possibilités!
2. Cet algorithme se limite à trois valeurs de prix par article (ptsart).
Or, dans la réalité, ce nombre n'est pas fixe: il peut être de 1, 2, 3,
Quelqu'un peut-il m'aider à résoudre ce problème?
Je ne vois pas de solution pour le 1er problème.
Pour le second, il me
semble qu'il faut passer par la récursivité mais je ne m'en sors pas...
> J'ai déjà consulté les archives du forum et j'ai déjà trouvé la fonction
> récursive de Fabrice qui fait cela en partie.
>
> Néanmoins, je pense que ce problème est plus complexe car:
>
> 1. Il ne faut pas forcément arriver au nombre de points total à utiliser
> mais sans approcher au plus, sans toutefois le dépasser. Ainsi, par
exemple,
>
> 2. LA quantité d'articles achetés est limité. On doit donc, à l'inverse
> problème de B. Neve, fixer des limites par article qui sont
> les quantités des divers articles achetés par le client (dans notre
exemple
> 3A, 1B et 5C).
Cet algo fonctionne mais il y a, à mes yeux, deux problèmes:
1. Le nombre d'essais pour trouver la solution peut être élevé car, malgré
certains tests, le principe est de tester TOUTES les possibilités!
2. Cet algorithme se limite à trois valeurs de prix par article (ptsart).
Or, dans la réalité, ce nombre n'est pas fixe: il peut être de 1, 2, 3,
Quelqu'un peut-il m'aider à résoudre ce problème?
Je ne vois pas de solution pour le 1er problème.
Pour le second, il me
semble qu'il faut passer par la récursivité mais je ne m'en sors pas...
> J'ai déjà consulté les archives du forum et j'ai déjà trouvé la fonction
> récursive de Fabrice qui fait cela en partie.
>
> Néanmoins, je pense que ce problème est plus complexe car:
>
> 1. Il ne faut pas forcément arriver au nombre de points total à utiliser
> mais sans approcher au plus, sans toutefois le dépasser. Ainsi, par
exemple,
>
> 2. LA quantité d'articles achetés est limité. On doit donc, à l'inverse
> problème de B. Neve, fixer des limites par article qui sont
> les quantités des divers articles achetés par le client (dans notre
exemple
> 3A, 1B et 5C).
Cet algo fonctionne mais il y a, à mes yeux, deux problèmes:
1. Le nombre d'essais pour trouver la solution peut être élevé car, malgré
certains tests, le principe est de tester TOUTES les possibilités!
2. Cet algorithme se limite à trois valeurs de prix par article (ptsart).
Or, dans la réalité, ce nombre n'est pas fixe: il peut être de 1, 2, 3,
Quelqu'un peut-il m'aider à résoudre ce problème?
Je ne vois pas de solution pour le 1er problème.
Pour le second, il me
semble qu'il faut passer par la récursivité mais je ne m'en sors pas...
> J'ai déjà consulté les archives du forum et j'ai déjà trouvé la fonction
> récursive de Fabrice qui fait cela en partie.
>
> Néanmoins, je pense que ce problème est plus complexe car:
>
> 1. Il ne faut pas forcément arriver au nombre de points total à utiliser
> mais sans approcher au plus, sans toutefois le dépasser. Ainsi, par
exemple,
>
> 2. LA quantité d'articles achetés est limité. On doit donc, à l'inverse
> problème de B. Neve, fixer des limites par article qui sont
> les quantités des divers articles achetés par le client (dans notre
exemple
> 3A, 1B et 5C).
salut.
"François Semoulin" a écrit dans le message de
news:bscc8r$ehm$
(...)
>
> Cet algo fonctionne mais il y a, à mes yeux, deux problèmes:
> 1. Le nombre d'essais pour trouver la solution peut être élevé car, malgré
> certains tests, le principe est de tester TOUTES les possibilités!
Exact.
cela tiens a la classe du probleme que tu pose qui est : "trouver le
meilleur moyen"
Il serait plus rapide de chercher "un bon moyen" que "le meilleur moyen".
Mais tu n'as peut-etre pas le choix.
> 2. Cet algorithme se limite à trois valeurs de prix par article (ptsart).
> Or, dans la réalité, ce nombre n'est pas fixe: il peut être de 1, 2, 3,
...
Il faut donc utiliser un tableau dynamique, (ou autre structure dynamique,
mais un tableau est bien adapté)
>
> Quelqu'un peut-il m'aider à résoudre ce problème?
> Je ne vois pas de solution pour le 1er problème.
Je pense qu'il n'y en a pas. Il faudra optimiser au maximum, pour que ce
soit le moins lent possible.
>Pour le second, il me
> semble qu'il faut passer par la récursivité mais je ne m'en sors pas...
Je vais essayer de regarder dans le detail du probleme pour te mettre sur la
voie.
Mais je pense qu'on va arriver a presque la meme chose que l'autre algo
(celui avec le conditionnement)
Il y a toutefois une difference.
Avec le conditionnement, on voulait trouver un conditionnement. On pouvait
donc sortir des qu'on en trouvait un.
Ici, on veut trouver le meilleur, on doit donc tout parcourir, et a chaque
fois qu'on en trouve un, le comparer avec le dernier trouvé pour voir si il
est meilleur.
sinon dans l'idee, ce sera le meme algo.
(...)
> > J'ai déjà consulté les archives du forum et j'ai déjà trouvé la fonction
> > récursive de Fabrice qui fait cela en partie.
> >
> > Néanmoins, je pense que ce problème est plus complexe car:
> >
> > 1. Il ne faut pas forcément arriver au nombre de points total à utiliser
> > mais sans approcher au plus, sans toutefois le dépasser. Ainsi, par
> exemple,
grosso modo, ca fait un test a changer dans la condition d'arret : changer
un tant que pas > en tant que < >
(...)
> >
> > 2. LA quantité d'articles achetés est limité. On doit donc, à l'inverse
du
> > problème de B. Neve, fixer des limites par article qui sont
respectivement
> > les quantités des divers articles achetés par le client (dans notre
exemple
> > 3A, 1B et 5C).
Dans le probleme de B Neve, il y avait une limite aussi.
Elle etait determinee par le nombre d'articles a conditionner.
Par exemple, si il y avait 100 articles a conditionner, la limite de boites
de 25 etait 4.
Cette limite etait calculee par une division entiere si je me souviens,
alors que dans ton cas elle est à passer en argument.
(on ne sait pas a priori ce que va acheter le client)
Ca revient a compliquer le probleme de B Neve en supposant que celui qui met
en conditionnement dispose d'un nombre limité de chaque boite.
(en vrai, un nombre infini de boite ca n'existe pas, mais je crois qu'on
avait supposé qu'il y en avait assez)
Est-ce que tu pourrais definir ce qu'est le meilleur moyen d'utiliser les
points ?
deja, il faut en utiliser le plus possible...
Est-ce que :
- il faut que le client paye le moins cher possible ?
ou :
- il faut que le magasin fasse le plus de marge possible.
(ainsi, on peut encore compliquer, et prendre en compte la marge que le
magasin fait sur chaque article)
salut.
"François Semoulin" <francois@semoulin.com> a écrit dans le message de
news:bscc8r$ehm$1@news.worldonline.be...
(...)
>
> Cet algo fonctionne mais il y a, à mes yeux, deux problèmes:
> 1. Le nombre d'essais pour trouver la solution peut être élevé car, malgré
> certains tests, le principe est de tester TOUTES les possibilités!
Exact.
cela tiens a la classe du probleme que tu pose qui est : "trouver le
meilleur moyen"
Il serait plus rapide de chercher "un bon moyen" que "le meilleur moyen".
Mais tu n'as peut-etre pas le choix.
> 2. Cet algorithme se limite à trois valeurs de prix par article (ptsart).
> Or, dans la réalité, ce nombre n'est pas fixe: il peut être de 1, 2, 3,
...
Il faut donc utiliser un tableau dynamique, (ou autre structure dynamique,
mais un tableau est bien adapté)
>
> Quelqu'un peut-il m'aider à résoudre ce problème?
> Je ne vois pas de solution pour le 1er problème.
Je pense qu'il n'y en a pas. Il faudra optimiser au maximum, pour que ce
soit le moins lent possible.
>Pour le second, il me
> semble qu'il faut passer par la récursivité mais je ne m'en sors pas...
Je vais essayer de regarder dans le detail du probleme pour te mettre sur la
voie.
Mais je pense qu'on va arriver a presque la meme chose que l'autre algo
(celui avec le conditionnement)
Il y a toutefois une difference.
Avec le conditionnement, on voulait trouver un conditionnement. On pouvait
donc sortir des qu'on en trouvait un.
Ici, on veut trouver le meilleur, on doit donc tout parcourir, et a chaque
fois qu'on en trouve un, le comparer avec le dernier trouvé pour voir si il
est meilleur.
sinon dans l'idee, ce sera le meme algo.
(...)
> > J'ai déjà consulté les archives du forum et j'ai déjà trouvé la fonction
> > récursive de Fabrice qui fait cela en partie.
> >
> > Néanmoins, je pense que ce problème est plus complexe car:
> >
> > 1. Il ne faut pas forcément arriver au nombre de points total à utiliser
> > mais sans approcher au plus, sans toutefois le dépasser. Ainsi, par
> exemple,
grosso modo, ca fait un test a changer dans la condition d'arret : changer
un tant que pas > en tant que < >
(...)
> >
> > 2. LA quantité d'articles achetés est limité. On doit donc, à l'inverse
du
> > problème de B. Neve, fixer des limites par article qui sont
respectivement
> > les quantités des divers articles achetés par le client (dans notre
exemple
> > 3A, 1B et 5C).
Dans le probleme de B Neve, il y avait une limite aussi.
Elle etait determinee par le nombre d'articles a conditionner.
Par exemple, si il y avait 100 articles a conditionner, la limite de boites
de 25 etait 4.
Cette limite etait calculee par une division entiere si je me souviens,
alors que dans ton cas elle est à passer en argument.
(on ne sait pas a priori ce que va acheter le client)
Ca revient a compliquer le probleme de B Neve en supposant que celui qui met
en conditionnement dispose d'un nombre limité de chaque boite.
(en vrai, un nombre infini de boite ca n'existe pas, mais je crois qu'on
avait supposé qu'il y en avait assez)
Est-ce que tu pourrais definir ce qu'est le meilleur moyen d'utiliser les
points ?
deja, il faut en utiliser le plus possible...
Est-ce que :
- il faut que le client paye le moins cher possible ?
ou :
- il faut que le magasin fasse le plus de marge possible.
(ainsi, on peut encore compliquer, et prendre en compte la marge que le
magasin fait sur chaque article)
salut.
"François Semoulin" a écrit dans le message de
news:bscc8r$ehm$
(...)
>
> Cet algo fonctionne mais il y a, à mes yeux, deux problèmes:
> 1. Le nombre d'essais pour trouver la solution peut être élevé car, malgré
> certains tests, le principe est de tester TOUTES les possibilités!
Exact.
cela tiens a la classe du probleme que tu pose qui est : "trouver le
meilleur moyen"
Il serait plus rapide de chercher "un bon moyen" que "le meilleur moyen".
Mais tu n'as peut-etre pas le choix.
> 2. Cet algorithme se limite à trois valeurs de prix par article (ptsart).
> Or, dans la réalité, ce nombre n'est pas fixe: il peut être de 1, 2, 3,
...
Il faut donc utiliser un tableau dynamique, (ou autre structure dynamique,
mais un tableau est bien adapté)
>
> Quelqu'un peut-il m'aider à résoudre ce problème?
> Je ne vois pas de solution pour le 1er problème.
Je pense qu'il n'y en a pas. Il faudra optimiser au maximum, pour que ce
soit le moins lent possible.
>Pour le second, il me
> semble qu'il faut passer par la récursivité mais je ne m'en sors pas...
Je vais essayer de regarder dans le detail du probleme pour te mettre sur la
voie.
Mais je pense qu'on va arriver a presque la meme chose que l'autre algo
(celui avec le conditionnement)
Il y a toutefois une difference.
Avec le conditionnement, on voulait trouver un conditionnement. On pouvait
donc sortir des qu'on en trouvait un.
Ici, on veut trouver le meilleur, on doit donc tout parcourir, et a chaque
fois qu'on en trouve un, le comparer avec le dernier trouvé pour voir si il
est meilleur.
sinon dans l'idee, ce sera le meme algo.
(...)
> > J'ai déjà consulté les archives du forum et j'ai déjà trouvé la fonction
> > récursive de Fabrice qui fait cela en partie.
> >
> > Néanmoins, je pense que ce problème est plus complexe car:
> >
> > 1. Il ne faut pas forcément arriver au nombre de points total à utiliser
> > mais sans approcher au plus, sans toutefois le dépasser. Ainsi, par
> exemple,
grosso modo, ca fait un test a changer dans la condition d'arret : changer
un tant que pas > en tant que < >
(...)
> >
> > 2. LA quantité d'articles achetés est limité. On doit donc, à l'inverse
du
> > problème de B. Neve, fixer des limites par article qui sont
respectivement
> > les quantités des divers articles achetés par le client (dans notre
exemple
> > 3A, 1B et 5C).
Dans le probleme de B Neve, il y avait une limite aussi.
Elle etait determinee par le nombre d'articles a conditionner.
Par exemple, si il y avait 100 articles a conditionner, la limite de boites
de 25 etait 4.
Cette limite etait calculee par une division entiere si je me souviens,
alors que dans ton cas elle est à passer en argument.
(on ne sait pas a priori ce que va acheter le client)
Ca revient a compliquer le probleme de B Neve en supposant que celui qui met
en conditionnement dispose d'un nombre limité de chaque boite.
(en vrai, un nombre infini de boite ca n'existe pas, mais je crois qu'on
avait supposé qu'il y en avait assez)
Est-ce que tu pourrais definir ce qu'est le meilleur moyen d'utiliser les
points ?
deja, il faut en utiliser le plus possible...
Est-ce que :
- il faut que le client paye le moins cher possible ?
ou :
- il faut que le magasin fasse le plus de marge possible.
(ainsi, on peut encore compliquer, et prendre en compte la marge que le
magasin fait sur chaque article)
Bonjour.
Je suis à la recherche d'un algorithme WD pour réaliser le traitement
suivant:
En quelques mots, je dois trouver un algorithme permettant d'utiliser au
mieux des points de fidélité pour acheter des articles.
Voici l'explication du problème:
Le fichier ARTICLE contient des articles à vendre. Chaque article a un
en EURO, un prix en points de fidélité et un nombre de points de fidélité
octroyé à chaque unité vendue de cet article.
Lors de chaque vente, l'acheteur peut payer soit en EURO, soit en points
fidélité qu'il aura collectionné au cours de ses achats précédents.
Le problème est le suivant: Il faut optimiser le paiement en points de
fidélité. En d'autres mots, le logiciel doit spécifier dans la liste des
articles achetés par le client, lesquels il doit payer au moyen de ses
points de fidélité afin de les utiliser au mieux.
L'acheteur remet au vendeur tous ses points de fidélité. Le vendeur encode
dans le programme le nombre de points reçus.
Il faut à ce moment là que le logiciel, sur base des articles sélectionnés
par l'acheteur, optimise au mieux le paiement au moyen des points fidélité
remis, tout en sachant qu'un article ne peut être payé partiellement avec
des points de fidélité.
Exemple:
L'acheteur souhaite acheter les articles suivants:
Qtté Article Prix unitaire EUR Prix unitaire
points fidélité
3 A 2.50? 6pts
1 B 5? 15pts
5 C 0.6? 2pts
Le total de points fidélité nécessaire pour payer cet achat est de 43 (2x6
+1x15 + 5x2).
Imaginons que l'acheteur remette au vendeur 16 points de fidélité.
Question: Comment utiliser au mieux ces points pour payer cet achat?
Dans notre exemple, la meilleure utilisation est:
2xA + 2xC = 2x6 + 2x2 = 16 points, solde de points à utiliser = 0
J'ai déjà consulté les archives du forum et j'ai déjà trouvé la fonction
récursive de Fabrice qui fait cela en partie.
Néanmoins, je pense que ce problème est plus complexe car:
1. Il ne faut pas forcément arriver au nombre de points total à utiliser
mais sans approcher au plus, sans toutefois le dépasser. Ainsi, par
si l'acheteur remet 30 points au vendeur dans l'exemple cité, je pense que
l'on n'arrive pas à utiliser tous les points remis (30) mais qu'on arrive
mieux à 29 (1x15 + 2x6 + 1x2). Il faut dans ce cas que le logiciel me
l'utilisation optimale à faire des points tout en indiquant le solde de
points (1 dans ce cas) à rendre à l'acheteur.
2. LA quantité d'articles achetés est limité. On doit donc, à l'inverse du
problème de B. Neve, fixer des limites par article qui sont respectivement
les quantités des divers articles achetés par le client (dans notre
3A, 1B et 5C).
Après avoir bien analysé la fonction récursive de Fabrice, je n'arrive pas
trouver la solution.
Quelqu'un peut-il me donner un coup de pouce? Je cale...
Merci d'avance et Bonnes fêtes.
François
Bonjour.
Je suis à la recherche d'un algorithme WD pour réaliser le traitement
suivant:
En quelques mots, je dois trouver un algorithme permettant d'utiliser au
mieux des points de fidélité pour acheter des articles.
Voici l'explication du problème:
Le fichier ARTICLE contient des articles à vendre. Chaque article a un
en EURO, un prix en points de fidélité et un nombre de points de fidélité
octroyé à chaque unité vendue de cet article.
Lors de chaque vente, l'acheteur peut payer soit en EURO, soit en points
fidélité qu'il aura collectionné au cours de ses achats précédents.
Le problème est le suivant: Il faut optimiser le paiement en points de
fidélité. En d'autres mots, le logiciel doit spécifier dans la liste des
articles achetés par le client, lesquels il doit payer au moyen de ses
points de fidélité afin de les utiliser au mieux.
L'acheteur remet au vendeur tous ses points de fidélité. Le vendeur encode
dans le programme le nombre de points reçus.
Il faut à ce moment là que le logiciel, sur base des articles sélectionnés
par l'acheteur, optimise au mieux le paiement au moyen des points fidélité
remis, tout en sachant qu'un article ne peut être payé partiellement avec
des points de fidélité.
Exemple:
L'acheteur souhaite acheter les articles suivants:
Qtté Article Prix unitaire EUR Prix unitaire
points fidélité
3 A 2.50? 6pts
1 B 5? 15pts
5 C 0.6? 2pts
Le total de points fidélité nécessaire pour payer cet achat est de 43 (2x6
+1x15 + 5x2).
Imaginons que l'acheteur remette au vendeur 16 points de fidélité.
Question: Comment utiliser au mieux ces points pour payer cet achat?
Dans notre exemple, la meilleure utilisation est:
2xA + 2xC = 2x6 + 2x2 = 16 points, solde de points à utiliser = 0
J'ai déjà consulté les archives du forum et j'ai déjà trouvé la fonction
récursive de Fabrice qui fait cela en partie.
Néanmoins, je pense que ce problème est plus complexe car:
1. Il ne faut pas forcément arriver au nombre de points total à utiliser
mais sans approcher au plus, sans toutefois le dépasser. Ainsi, par
si l'acheteur remet 30 points au vendeur dans l'exemple cité, je pense que
l'on n'arrive pas à utiliser tous les points remis (30) mais qu'on arrive
mieux à 29 (1x15 + 2x6 + 1x2). Il faut dans ce cas que le logiciel me
l'utilisation optimale à faire des points tout en indiquant le solde de
points (1 dans ce cas) à rendre à l'acheteur.
2. LA quantité d'articles achetés est limité. On doit donc, à l'inverse du
problème de B. Neve, fixer des limites par article qui sont respectivement
les quantités des divers articles achetés par le client (dans notre
3A, 1B et 5C).
Après avoir bien analysé la fonction récursive de Fabrice, je n'arrive pas
trouver la solution.
Quelqu'un peut-il me donner un coup de pouce? Je cale...
Merci d'avance et Bonnes fêtes.
François
Bonjour.
Je suis à la recherche d'un algorithme WD pour réaliser le traitement
suivant:
En quelques mots, je dois trouver un algorithme permettant d'utiliser au
mieux des points de fidélité pour acheter des articles.
Voici l'explication du problème:
Le fichier ARTICLE contient des articles à vendre. Chaque article a un
en EURO, un prix en points de fidélité et un nombre de points de fidélité
octroyé à chaque unité vendue de cet article.
Lors de chaque vente, l'acheteur peut payer soit en EURO, soit en points
fidélité qu'il aura collectionné au cours de ses achats précédents.
Le problème est le suivant: Il faut optimiser le paiement en points de
fidélité. En d'autres mots, le logiciel doit spécifier dans la liste des
articles achetés par le client, lesquels il doit payer au moyen de ses
points de fidélité afin de les utiliser au mieux.
L'acheteur remet au vendeur tous ses points de fidélité. Le vendeur encode
dans le programme le nombre de points reçus.
Il faut à ce moment là que le logiciel, sur base des articles sélectionnés
par l'acheteur, optimise au mieux le paiement au moyen des points fidélité
remis, tout en sachant qu'un article ne peut être payé partiellement avec
des points de fidélité.
Exemple:
L'acheteur souhaite acheter les articles suivants:
Qtté Article Prix unitaire EUR Prix unitaire
points fidélité
3 A 2.50? 6pts
1 B 5? 15pts
5 C 0.6? 2pts
Le total de points fidélité nécessaire pour payer cet achat est de 43 (2x6
+1x15 + 5x2).
Imaginons que l'acheteur remette au vendeur 16 points de fidélité.
Question: Comment utiliser au mieux ces points pour payer cet achat?
Dans notre exemple, la meilleure utilisation est:
2xA + 2xC = 2x6 + 2x2 = 16 points, solde de points à utiliser = 0
J'ai déjà consulté les archives du forum et j'ai déjà trouvé la fonction
récursive de Fabrice qui fait cela en partie.
Néanmoins, je pense que ce problème est plus complexe car:
1. Il ne faut pas forcément arriver au nombre de points total à utiliser
mais sans approcher au plus, sans toutefois le dépasser. Ainsi, par
si l'acheteur remet 30 points au vendeur dans l'exemple cité, je pense que
l'on n'arrive pas à utiliser tous les points remis (30) mais qu'on arrive
mieux à 29 (1x15 + 2x6 + 1x2). Il faut dans ce cas que le logiciel me
l'utilisation optimale à faire des points tout en indiquant le solde de
points (1 dans ce cas) à rendre à l'acheteur.
2. LA quantité d'articles achetés est limité. On doit donc, à l'inverse du
problème de B. Neve, fixer des limites par article qui sont respectivement
les quantités des divers articles achetés par le client (dans notre
3A, 1B et 5C).
Après avoir bien analysé la fonction récursive de Fabrice, je n'arrive pas
trouver la solution.
Quelqu'un peut-il me donner un coup de pouce? Je cale...
Merci d'avance et Bonnes fêtes.
François
Bonjour.
Merci de ta réponse Fabrice.
Je reviens sur les deux problèmes que je rencontre.
Problème 1: parcours des solutions possibles pour trouver la solution
optimale.
Après y avoir réflechi, je pense que:
A. La solution est optimale si tous les points remis par l'acheteur
sont utilisés pour acheter les articles choisis, ce qui revient à dire
qu'à mon avis, il faut tester en premier l'algorithme que tu as mis au
point pour B Neve. Si celui-ci donne le résultat, il est inutile de
chercher plus loin une autre solution puisque dans ce cas, tous les
points sont utilisés.
B. S'il est impossible d'utiliser tous les points remis (cas pour
lequel ton alogo renvoie "ah ben non alors"), il faut dans ce cas
commencer à passer toutes les possibilités en revue afin de trouver la
meilleure solution possible.
Pour cela aussi, j'ai trouvé un moyen
d'optimiser. Tu verras que dans chaque boucle POUR de ma procédure
j'ai testé le nombre de points calculés.
En effet, comme chaque boucle
POUR incrémente de façon CROISSANTE les indices, il est facile
d'arrêter la boucle dès que le nombre de points calculés par l'algo
est supérieur au nombre de points remis par l'acheteur.
Cela limite donc les solutions parcourues mais néanmoins, le nombre
peut encore être élevé.
Voilà où j'en suis actuellement. Vois-tu d'autres façons d'optimiser?
Par contre pour le 2ème problème de nombre d'articles ayant des prix
en points différents, je n'ai pas trouvé de solution... j'ai en fait
du mal à conceptualiser la récusrivité dans la gestion des boucles
pour imbriqueés...
Bonjour.
Merci de ta réponse Fabrice.
Je reviens sur les deux problèmes que je rencontre.
Problème 1: parcours des solutions possibles pour trouver la solution
optimale.
Après y avoir réflechi, je pense que:
A. La solution est optimale si tous les points remis par l'acheteur
sont utilisés pour acheter les articles choisis, ce qui revient à dire
qu'à mon avis, il faut tester en premier l'algorithme que tu as mis au
point pour B Neve. Si celui-ci donne le résultat, il est inutile de
chercher plus loin une autre solution puisque dans ce cas, tous les
points sont utilisés.
B. S'il est impossible d'utiliser tous les points remis (cas pour
lequel ton alogo renvoie "ah ben non alors"), il faut dans ce cas
commencer à passer toutes les possibilités en revue afin de trouver la
meilleure solution possible.
Pour cela aussi, j'ai trouvé un moyen
d'optimiser. Tu verras que dans chaque boucle POUR de ma procédure
j'ai testé le nombre de points calculés.
En effet, comme chaque boucle
POUR incrémente de façon CROISSANTE les indices, il est facile
d'arrêter la boucle dès que le nombre de points calculés par l'algo
est supérieur au nombre de points remis par l'acheteur.
Cela limite donc les solutions parcourues mais néanmoins, le nombre
peut encore être élevé.
Voilà où j'en suis actuellement. Vois-tu d'autres façons d'optimiser?
Par contre pour le 2ème problème de nombre d'articles ayant des prix
en points différents, je n'ai pas trouvé de solution... j'ai en fait
du mal à conceptualiser la récusrivité dans la gestion des boucles
pour imbriqueés...
Bonjour.
Merci de ta réponse Fabrice.
Je reviens sur les deux problèmes que je rencontre.
Problème 1: parcours des solutions possibles pour trouver la solution
optimale.
Après y avoir réflechi, je pense que:
A. La solution est optimale si tous les points remis par l'acheteur
sont utilisés pour acheter les articles choisis, ce qui revient à dire
qu'à mon avis, il faut tester en premier l'algorithme que tu as mis au
point pour B Neve. Si celui-ci donne le résultat, il est inutile de
chercher plus loin une autre solution puisque dans ce cas, tous les
points sont utilisés.
B. S'il est impossible d'utiliser tous les points remis (cas pour
lequel ton alogo renvoie "ah ben non alors"), il faut dans ce cas
commencer à passer toutes les possibilités en revue afin de trouver la
meilleure solution possible.
Pour cela aussi, j'ai trouvé un moyen
d'optimiser. Tu verras que dans chaque boucle POUR de ma procédure
j'ai testé le nombre de points calculés.
En effet, comme chaque boucle
POUR incrémente de façon CROISSANTE les indices, il est facile
d'arrêter la boucle dès que le nombre de points calculés par l'algo
est supérieur au nombre de points remis par l'acheteur.
Cela limite donc les solutions parcourues mais néanmoins, le nombre
peut encore être élevé.
Voilà où j'en suis actuellement. Vois-tu d'autres façons d'optimiser?
Par contre pour le 2ème problème de nombre d'articles ayant des prix
en points différents, je n'ai pas trouvé de solution... j'ai en fait
du mal à conceptualiser la récusrivité dans la gestion des boucles
pour imbriqueés...
>
(ah oui au fait... Le recuit j'en avait entendu parler mais je me souviens
plus)
>
(ah oui au fait... Le recuit j'en avait entendu parler mais je me souviens
plus)
>
(ah oui au fait... Le recuit j'en avait entendu parler mais je me souviens
plus)
>
> (ah oui au fait... Le recuit j'en avait entendu parler mais je me
> plus)
Pour info, c'est un pb d'optimisation capable d'être résolu à l'aide du
simplexe. Du moment que tu as une fonction à minimiser (ou maximiser), des
contraites suffisantes à vérifier...
Ensuite pour trouver des solutions les meilleures tu as les méthodes
heuristiques et méta heuristiques, très utiles pour les pbs NP complets.
à par exmeple : le recuit simulé, les algo génétiques, l'algo tabou, ...
Emmanuel
>
> (ah oui au fait... Le recuit j'en avait entendu parler mais je me
> plus)
Pour info, c'est un pb d'optimisation capable d'être résolu à l'aide du
simplexe. Du moment que tu as une fonction à minimiser (ou maximiser), des
contraites suffisantes à vérifier...
Ensuite pour trouver des solutions les meilleures tu as les méthodes
heuristiques et méta heuristiques, très utiles pour les pbs NP complets.
à par exmeple : le recuit simulé, les algo génétiques, l'algo tabou, ...
Emmanuel
>
> (ah oui au fait... Le recuit j'en avait entendu parler mais je me
> plus)
Pour info, c'est un pb d'optimisation capable d'être résolu à l'aide du
simplexe. Du moment que tu as une fonction à minimiser (ou maximiser), des
contraites suffisantes à vérifier...
Ensuite pour trouver des solutions les meilleures tu as les méthodes
heuristiques et méta heuristiques, très utiles pour les pbs NP complets.
à par exmeple : le recuit simulé, les algo génétiques, l'algo tabou, ...
Emmanuel
Alors voila le probleme.
le client vient payer N articles.
il a P points de fidelite.
parmi ses N articles,
il y a N1 articles a P1 points
N2 articles a P2 points
etc
On veut qu'il utilise le plus possible de points de fidelite.
Combien faut t'il utiliser d'articles à P1, P2 etc points ?
Comment aborder ce probleme ?
2 parties :
1)On veut essayer toutes les combinaisons,
2)pour trouver la meilleure.
procedure parcourir_solutions (tb_articles, nb_articles_tb, local
points_restants)
// renvoi les points utilises
pour i = tb_articles[nb_articles_tb].nb_articles à 0 pas -1
points_restant_tempo = points_restant -
tb_articles[nb_articles_tb].valeur_points
parcourir_solutions(tb_articles,nb_articles_tb -1,
points_restant_tempo)
fin
fin
Alors voila le probleme.
le client vient payer N articles.
il a P points de fidelite.
parmi ses N articles,
il y a N1 articles a P1 points
N2 articles a P2 points
etc
On veut qu'il utilise le plus possible de points de fidelite.
Combien faut t'il utiliser d'articles à P1, P2 etc points ?
Comment aborder ce probleme ?
2 parties :
1)On veut essayer toutes les combinaisons,
2)pour trouver la meilleure.
procedure parcourir_solutions (tb_articles, nb_articles_tb, local
points_restants)
// renvoi les points utilises
pour i = tb_articles[nb_articles_tb].nb_articles à 0 pas -1
points_restant_tempo = points_restant -
tb_articles[nb_articles_tb].valeur_points
parcourir_solutions(tb_articles,nb_articles_tb -1,
points_restant_tempo)
fin
fin
Alors voila le probleme.
le client vient payer N articles.
il a P points de fidelite.
parmi ses N articles,
il y a N1 articles a P1 points
N2 articles a P2 points
etc
On veut qu'il utilise le plus possible de points de fidelite.
Combien faut t'il utiliser d'articles à P1, P2 etc points ?
Comment aborder ce probleme ?
2 parties :
1)On veut essayer toutes les combinaisons,
2)pour trouver la meilleure.
procedure parcourir_solutions (tb_articles, nb_articles_tb, local
points_restants)
// renvoi les points utilises
pour i = tb_articles[nb_articles_tb].nb_articles à 0 pas -1
points_restant_tempo = points_restant -
tb_articles[nb_articles_tb].valeur_points
parcourir_solutions(tb_articles,nb_articles_tb -1,
points_restant_tempo)
fin
fin
procedure trouve_meilleure (tb_article, nb_articles_tb, local
points_restants, tb_meilleur)
// tb_meilleur va contenir n1,n2,n3 etc. il doit etre remmpli de 0 au
si nb_article_tb = 0 alors retour
tb_meilleur_tempo est un tableau de nb_articles_tb-1 entiers
meilleur_tb_meilleur est un tableu de nb_articles_tb entiers
pour i = tb_articles[nb_articles_tb].nb_articles à 0 pas -1
trouve_meilleur(tb_articles,nb_articles_tb -1,
points_restant_tempo,tb_meilleur_tempo)
si nb_article_tb = 0 alors retour
tb_meilleur_tempo est un tableau de nb_articles_tb-1 entiers
procedure trouve_meilleure (tb_article, nb_articles_tb, local
points_restants, tb_meilleur)
// tb_meilleur va contenir n1,n2,n3 etc. il doit etre remmpli de 0 au
si nb_article_tb = 0 alors retour
tb_meilleur_tempo est un tableau de nb_articles_tb-1 entiers
meilleur_tb_meilleur est un tableu de nb_articles_tb entiers
pour i = tb_articles[nb_articles_tb].nb_articles à 0 pas -1
trouve_meilleur(tb_articles,nb_articles_tb -1,
points_restant_tempo,tb_meilleur_tempo)
si nb_article_tb = 0 alors retour
tb_meilleur_tempo est un tableau de nb_articles_tb-1 entiers
procedure trouve_meilleure (tb_article, nb_articles_tb, local
points_restants, tb_meilleur)
// tb_meilleur va contenir n1,n2,n3 etc. il doit etre remmpli de 0 au
si nb_article_tb = 0 alors retour
tb_meilleur_tempo est un tableau de nb_articles_tb-1 entiers
meilleur_tb_meilleur est un tableu de nb_articles_tb entiers
pour i = tb_articles[nb_articles_tb].nb_articles à 0 pas -1
trouve_meilleur(tb_articles,nb_articles_tb -1,
points_restant_tempo,tb_meilleur_tempo)
si nb_article_tb = 0 alors retour
tb_meilleur_tempo est un tableau de nb_articles_tb-1 entiers