un algo pour rendre la monnaie

Version imprimable

18/09/2008, 17h09
r0d

un algo pour rendre la monnaie

Bonjour à tous,

voilà. Je bloque sur un algo qui semblait facile à première vue, mais qui s'avère plus ardu que ce que je pensais. Je vais essayer d'énoncer le problème le plus clairement possible:

- j'utiliserai le mot monnaie dans le sens "une pièce ou un billet"
- j'utiliserai le mot change dans le sens "différence entre l'argent inséré par l'utilisateur et le prix du produit"
- l'unité de base est le centime d'euro, on évite ainsi les flottants.
- j'ai une table de monnaies disponibles (appelons-là TDispo): pour chaque valeur (1, 2, 5, ...,20.000, 50.000 (50.000 cts = 500€) ) on a un nombre de monnaie disponible, c'est à dire que l'on peut utiliser pour rendre le change.
- C1: on doit calculer la façon optimale de rendre le change, c'est à dire avec le moins de monnaies possibles.
- C2: s'il est possible de rendre le change, on ne doit pas dire que ce n'est pas possible (contrainte plus importante qu'il n'y parait)

Pour l'instant j'ai un algoritthme "glouton" qui fonctionne à peu près, mais s'il respecte C1, parfois il ne respecte pas C2:

Citation:

reste := change
Tant que reste>0
| prendre la plus grande monnaie possible (pgmp) dans TDispo telle que pgmp<reste
| si pgmp<0 (n'existe pas)
| | break
| sinon
| | res[pgmp]++
| | reste -= pgmp

Si reste == 0 c'est ok, sinon c'est pas ok

avec:
change = somme à retourner
res = table dans laquelle on stocke le résultat du calcul (sa structure est la même que TDispo )

Cet algo ne fonctionne pas, par exemple, dans le cas où on dois rendre 80cts et qu'on a disponible (TDisp): 1 piece de 50cts et 4 pieces de 20cts

J'ai bien cherché partout, mais j'ai rien trouvé d'exploitable. Si quelqu'un est plus habile que moi en recherche... ça doit bien se trouver non?

Sinon toute proposition est la bienvenue :)
:merci:
18/09/2008, 17h45
khayyam90

Bien le bonjour,

La première idée est de posséder suffisamment de pièces de chaque sorte pour être sûr de satisfaire C2, il faut donc régulièrement réapprovisionner la machine. :D

L'idée qui me vient à l'esprit pour satisfaire ta contrainte C2 est de procéder par programmation dynamique, en recherchant toutes les possibilités que l'on a de rendre la monnaie.

On doit déterminer comment rendre une somme S
trouverAgencementPourS(s) :
boucler sur toutes pièces non utilisées et qui ne soient pas trop importantes par rapport à S
déterminer pour chacune d'elles la somme qu'il resterait à rendre
tenir à jour une liste des pièces utilisées
trouverAgencementPourS(cette nouvelle somme)

A la gestion de la liste solution près, tu obtiendras toutes les combinaisons possibles. La combinaison de moindre longueur et dont la somme est ton prix de départ sera ta solution. Attention, l'algo est en O(n!) avec n le nombre de pièces que tu as ta disposition. Résultat exact qui satisfait à C1 et C2.

Une solution moins barbare consisterait à prendre ton algorithme puis à essayer de le résoudre en retirant du jeu une par une les pièces trouvées pécédemment lorsque C2 n'est plus vérifiée.
18/09/2008, 18h41
SpiceGuid
Un petit peu d'analyse rétrograde devrait suffir:
- 1 = 1
- 2 = ( 2 | 1+1 )
- 3 = ( 2+1 | 1+1+1 )
- 4 = ( 2+2 | 2+1+1 | 1+1+1+1 )
- 5 = ( 5 | 2+2+1 | 2+1+1+1 | 1+1+1+1+1 )
- 6 = ( 5+1 | 4+2 ) // à développer en substituant 4 et 5
- 7 = ( 6+1 | 5+2 ) // à développer en substituant 5 et 6
- 8 = ( 7+1 | 6+2 ) // à développer en substituant 6 et 7
- 9 = ( 8+1 | 7+2 ) // à développer en substituant 7 et 8
Tu n'as plus qu'à rendre la monnaie en progressant dans les puissances de dix: 0.01€, 0.1€, 1€, 10€, 100€, 1000€,...
18/09/2008, 18h58
r0d

@khayyam90: ta solution devrait fonctionner, mais c'est trop gourmand. Pour l'instant, je suis parti sur un truc totalement "artisanal". Mais ça marche plutôt bien, mais il y a encore des cas qui ne fonctionnent pas. Ce que je fais, c'est ce que tu as dit: j'améliore mon algo du premier post pour que, dans les cas où ça ne marche pas, il cherche une aute combinaison. Le truc c'est qu'au final, je n'ai pas tant de type de monnaie que ça, je peux donc feinter sur des cas particuliers. En plus ça optimise le code :aie:

Mais bon, j'aurais bien aimé trouver un truc propre :)

@SpiceGuid: j'y ai pensé mais avec cette méthode je ne vois pas comment assurer que C1 soit vérifié.
18/09/2008, 19h27
plegat

Salut,

Citation:

Envoyé par r0d

Cet algo ne fonctionne pas, par exemple, dans le cas où on dois rendre 80cts et qu'on a disponible (TDisp): 1 piece de 50cts et 4 pieces de 20cts

Je dois être tordu... ou fatigué...

80 cts... pgmp=50, reste 30 cts, et quatre pièces de 20 cts
30 cts... pgmp=20, reste 10 cts, et trois pièces de 20 cts
10 cts... pgmp=0, reste 10 => break

Ton algorithme fonctionne bien.
Il est où le problème?
18/09/2008, 19h56
r0d

Citation:

Envoyé par plegat

Je dois être tordu... ou fatigué...

ou je me suis trompé :oops: mais je ne crois pas:

Citation:

Envoyé par plegat

80 cts... pgmp=50, reste 30 cts, et quatre pièces de 20 cts
30 cts... pgmp=20, reste 10 cts, et trois pièces de 20 cts
10 cts... pgmp=0, reste 10 => break

Il reste 10cts, alros qu'il devrait rester 0. Si le gars je lui rend 70cts alors que je devrais lui rendre 80cts, il va pas être content :aie:
18/09/2008, 20h12
pseudocode

Citation:

Envoyé par plegat

80 cts... pgmp=50, reste 30 cts, et quatre pièces de 20 cts
30 cts... pgmp=20, reste 10 cts, et trois pièces de 20 cts
10 cts... pgmp=0, reste 10 => break

impossible de rendre 10cts, car on n'a que des pieces de 20cts. :aie:

Sinon, pour le problème du P.O : un algo glouton avec du backtracking en cas d'échec. La ère solution trouvée sera optimum car le système monétaire utilisé est canonique. ;)
18/09/2008, 22h57
plegat

Citation:

Envoyé par r0d

Il reste 10cts, alros qu'il devrait rester 0. Si le gars je lui rend 70cts alors que je devrais lui rendre 80cts, il va pas être content :aie:

Au temps pour moins, je viens de piger ton contre-exemple! :aie:
Je n'avais pas vu qu'on pouvait rendre les 80 directement avec les pièces de 20!
Fatigué moi...

Dans ce cas... pourquoi ne pas enlever une pièce de plus forte valeur parmi les pièces dispo et refaire un glouton? (voire boucler si nécessaire)
Sur les 80cts, si tu enlèves une pièces de 50 (première valeur inférieure), tu te retrouves avec tes pièces de 20...
Par contre, est-ce que ce serait l'optimale de second ordre dans tous les cas...?
19/09/2008, 10h01
Furikawari

C'est un sac à dos ce problème non ?

Glouton avec backtracking

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public static int[] solve(int[] values, int[] dispos, int entry) {
 
	// sauvegarde de la meilleure solution
	int bestscore = Integer.MAX_VALUE;
	int[] bestsolution = null;
 
	// recherche des solutions possibles
	int[] solution = new int[values.length];
	int start = 0, score = 0;
 
	while(start>=0) {
		// glouton
		for(int i=start;i<values.length;i++) {
			solution[i]= Math.min( entry/values[i] , dispos[i]);
			entry = entry - solution[i]*values[i];
			score = score + solution[i];
		}
 
		// une solution a été trouvée
		if (entry==0) {
			// on la conserve si c'est la meilleure
			if (score<bestscore) {
				bestscore=score;
				bestsolution=Arrays.copyOf(solution, solution.length);
			}
		}
 
		// backtrack
		start = values.length-1;
		while(start>=0 && solution[start]==0) start=start-1;
 
		// annulation de la dernière operation
		if (start>=0) {
			solution[start]=solution[start]-1;
			score = score - 1;
			entry = entry + values[start];
			start=start+1;
		}
	}
 
	return bestsolution;
}

Utilisation dans le cas qui nous interesse:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// INPUT: valeurs et nombre de pieces disponibles
int[] values   = new int[] {100,50,20,10,5,2,1};
int[] dispos   = new int[] {  0, 5, 5, 0,0,0,0};
 
// INPUT: valeur a rendre 
int entry = 80;
 
// resolution du problème
int[] solution = solve(values,dispos,entry);
if (solution!=null) {
	System.out.print(Arrays.toString(solution));
} else {
	System.out.println("pas de solution");
}

ce qui nous affiche: [0, 0, 4, 0, 0, 0, 0], c'est à dire qu'il faut rendre 4 pieces de 20.

Une solution en Haskell :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
type Value = Int -- value of a piece
type Reserve = [(Value,Int)] -- couple of (piece value, number of such piece)
type Solution = [(Value,Int)] -- solutions are from the same form
 
-- the above types can't express an important invariant :
-- the value should be ordered in decreasing order and form a canonic system
-- for the algorithm to deliver correct responses correctly ordered
-- we would need a dependent type system to express those invariants in the types
 
-- we opted for a function that would use the eager algorithm to
-- deliver all solutions, the optimal first
solve :: Value -> Reserve -> [Solution]
solve 0 [] = [[]]
solve value [] = []
solve value ((pieceValue, amount) : pieces) = 
    concatMap forAGivenAmount [maxAmount, maxAmount - 1 .. 0]
    where maxAmount = min (value `div` pieceValue) amount
          forAGivenAmount solAmount = 
              map ((pieceValue,solAmount) :) 
                      $ solve (value - pieceValue * solAmount) pieces
 
 
main = print . head $ solve 80 [(100,0), (50,5), (20,5), (10,0), (5,0), (2,0), (1,0)]

solve() nous retourne une liste de toutes les solutions (l'optimale venant en premier si les invariants énoncés sont respectés) mais l'évaluation paresseuse employée par Haskell signifie que si je demande seulement la première valeur de la liste (l'optimale), seule celle-ci sera vraiment calculée.

--
Jedaï

19/09/2008, 22h37
CedricMocquillon

Effectivement, ton problème est une variation du problème de sac à dos et au vu du papier :
http://www.jstor.org/pss/2583204
a priori, il doit être NP-Difficile au sens fort... donc tu n'as pas le choix, il va falloir énumérer les solutions comme l'ont proposé pseudocode et Jedai. Après tu peux toujours utiliser des solutions à base de modélisation mathématique qui se chargeront pour toi de construire l'arbre de recherche et d'élaguer les branches en fonction de conditions de coupes génériques (glpk est gratuit, sinon y'a aussi Cplex, Xpress-MP (payant)....). Ou alors il te faudra coder toi même ta procédure par séparation et évaluation et développer des bornes inférieures pour pouvoir élaguer ton arbre de recherche... Dernière solution: accepter de violer dans certains cas ta condition C2...
19/09/2008, 22h56
SpiceGuid

Souvent, quand je lis le code de Jedaï :king: je me dis qu'il faudrait que j'arrête de programmer dans un langage de bas niveau, d'une certaine façon OCaml reste souvent trop impératif :(
20/09/2008, 15h31
méphistopheles

Citation:

Envoyé par CedricMocquillon

donc tu n'as pas le choix, il va falloir énumérer les solutions comme l'ont proposé pseudocode et Jedai.

Il me semble que des études ont prouvé que l'algorithme glouton étais optimal avec la monnaie européenne: http://www.larecherche.fr/content/re...ticle?id=22986

Tu pourrais donc appliquer l'ago glouton jusqu'à ce que celui-ci ne permette pas de résoudre le problème auquel cas, tu devra supposer une premières pièces différente, retenter le glouton etc...

A la limite, tester toutes les possibilités lorsque le glouton échoue ne devrais pas être trop long à condition que ce ne soient pas les stock de "petite monnaie" qui soient épuisés...

Je pense aussi qu'une part de statistique est nécessaire pour pouvoir évaluer la chose: les gens, auron, il me semble, plus facilement tendance à utiliser les "grosses pièces" que les petites pour payer, ce qui veut dire que celles-ci pourraient etre la seule chose à réapprovisionner...

sinon, beaucoup plus simple, n'accepter qu'un type de pièce :aie:

en tout cas, je te souhaite bonne chance
20/09/2008, 19h19
pseudocode

Citation:

Envoyé par méphistopheles

Il me semble que des études ont prouvé que l'algorithme glouton étais optimal avec la monnaie européenne: http://www.larecherche.fr/content/re...ticle?id=22986

a rendre: 80 cts

--- dispo ---
1 euro: 0
50 cts: 10
20 cts: 10
10 cts: 0
5 cts: 0
1 cts: 10

--- résultat du glouton ---
1*50 cts + 1*20cts + 10*1cts = 12 pieces

--- optimum ---
4*20cts = 4 pieces
20/09/2008, 19h26
méphistopheles

oui, le glouton suppose qu'on à encore les pièces intermédiaires, s'il y a un trou, le glouton ne s'applique plus

mais dans le cas, "le plus courant" on peut l'utiliser.
Dans les autres, l'arbre de possibilités est plus petit et donc on peut, je pense, le calculer
20/09/2008, 19h28
CedricMocquillon

En fait dans l'article de la recherche, les auteurs considèrent le cas sans limite de capacité, dans ce cas pour rendre 80 cts le glouton donnera bien 1*50+1*20+1*10 et donc 3 pièces. C'est quand même intéressant de considérer que le problème de sac à dos avec contrainte d'égalité sans capacité peut avoir des ensembles d'instances pour lesquels l'algorithme glouton est optimal (le cas de la monnaie européenne).
20/09/2008, 19h50
pseudocode

Citation:

Envoyé par CedricMocquillon

C'est quand même intéressant de considérer que le problème de sac à dos avec contrainte d'égalité sans capacité peut avoir des ensembles d'instances pour lesquels l'algorithme glouton est optimal (le cas de la monnaie européenne).

ca marche pour pas mal de configuration de pieces:

Optimality of Greedy Change-Making

A polynomial-time algorithm for the change-making problem

Mouais... Donc l'algo glouton n'est pas suffisant... Voici un algo qui marche, mais je ne sais pas si on peut faire mieux :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
type Value = Int -- value of a piece
type Reserve = [(Value,Int)] -- couple of (piece value, number of such piece)
type Solution = [(Value,Int)] -- solutions are from the same form
 
-- all solutions ordered by the number of pieces used
solve :: Value -> Reserve -> [Solution]
solve 0 [] = [[]]
solve value [] = []
solve value ((pieceValue, amount) : pieces) = 
    foldr merge [] $ map forAGivenAmount [maxAmount, maxAmount - 1 .. 0]
    where maxAmount = min (value `div` pieceValue) amount
          forAGivenAmount solAmount = 
              map ((pieceValue,solAmount) :) 
                      $ solve (value - pieceValue * solAmount) pieces
          merge [] ys = ys
          merge xs [] = xs
          merge xs@(x:xs') ys@(y:ys') 
              | score x < score y = x : merge xs' ys
              | otherwise         = y : merge xs ys'
          score = sum . map snd
 
main = print . head $ solve 80 [(100,0), (50,5), (20,5), (10,0), (5,0), (2,0), (1,0)]

--
Jedaï

20/09/2008, 19h54
méphistopheles

Citation:

Envoyé par pseudocode

ca marche pour pas mal de configuration de pieces:

Optimality of Greedy Change-Making

A polynomial-time algorithm for the change-making problem

heuu... les deux liens correspondent à la même adresse...:?

Citation:

Envoyé par Jedai

Voici un algo qui marche

Serais-il possible de le traduire légerement en langage algo ?
J'avoue ne pas y comprendre grand chose :oops:
20/09/2008, 20h03
Jedai

Citation:

Envoyé par méphistopheles

Serais-il possible de le traduire légerement en langage algo ?
J'avoue ne pas y comprendre grand chose :oops:

Rien de mystérieux, il explore l'intégralité de l'espace des solutions (c'est du NP-difficile de toute façon) et trie les solutions, la seule optimisation c'est qu'il exploite un peu la structure de la récursion pour éviter certaines additions.

score compte le nombre de pièces dans une solution, merge mélange deux listes triées de solutions, forAGivenAmount renvoie la liste triée des solutions commençant par une certaine quantité de la pièce considérée par solve, maxAmount est juste la quantité maximale possible pour la pièce considérée (le minimum entre le nombre de pièce qu'on peut mettre dans la valeur à atteindre et le nombre de pièce réellement disponible).

Le coût n'est pas aussi horrible qu'on pourrait le penser dans des systèmes raisonnables, et l'évaluation paresseuse signifie que si on ne demande que l'optimum, le tri n'est pas vraiment effectué, il n'y a qu'une recherche de minimum, un peu optimisée.

--
Jedaï
20/09/2008, 20h08
méphistopheles

Ok, c'est juste le langage qui me rebutais (c'est pas une syntaxe classique).

à mon avis, il faut un algo qui utilise le glouton et bascule en NP-difficile lorsque qu'il manque une piece à l'algo glouton. (en reprenant du début) toutefois, il est peut être préférable de finir l'algo glouton pour s'en servir comme référence (si le nombre de pièces dans la branche devient superieur au minimum déja trouvé, on sort).
20/09/2008, 20h52
pseudocode

Citation:

Envoyé par méphistopheles

heuu... les deux liens correspondent à la même adresse...:?

Arg. Petite erreur de copier/coller. :aie:

http://demonstrations.wolfram.com/Op...dyChangeMaking

Genre :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
solve :: Value -> Reserve -> [Solution]
solve 0 [] = [[]]
solve value [] = []
solve value ps = 
    if eagerEnough v ps 
    then solve' concat value ps
    else solve' (foldr merge []) ps
   where eagerEnough v ps = undefined
 
solve' :: ([[Solution]] -> [Solution]) -> Value -> Reserve -> [Solution]
solve' combine value ((pieceValue, amount) : pieces) = 
    combine $ map forAGivenAmount [maxAmount, maxAmount - 1 .. 0]
   where maxAmount = min (value `div` pieceValue) amount
         forAGivenAmount solAmount = 
             map ((pieceValue,solAmount) :) 
                     $ solve (value - pieceValue * solAmount) pieces
 
merge [] ys = ys
merge xs [] = xs
merge xs@(x:xs') ys@(y:ys') 
  | score x < score y = x : merge xs' ys
  | otherwise         = y : merge xs ys'
   where score = sum . map snd

La fonction "eagerEnough" est laissée en exercice au lecteur courageux des articles cités par PseudoCode.

--
Jedaï

20/09/2008, 21h00
pseudocode

Citation:

Envoyé par Jedai

La fonction "eagerEnough" est laissée en exercice au lecteur courageux des articles cités par PseudoCode.

Heu... je vais en rester a ma version Java si ca ne te dérange pas. :aie:
22/09/2008, 23h20
coyotte507

Algo en n^(log10(2))*log10(n)???
Bonjour,

je viens avec la solution que j'ai trouvée...
Je ne suis pas expert, donc bon, il y a peut-être une erreur mais je ne pense pas.

Je vais essayer d'expliquer le principe de mon algorithme:

Quand on rends des pièces, le risque le plus grand de ne pas pouvoir rendre les pièces est l'absence de petite monnaie.
Ainsi, si je dois rendre un Euro et un centime, et que je n'ai pas de pièces de 1-2 centimes, c'est raté!

Donc pour pouvoir rendre la monnaie, il faut déjà pouvoir éliminer les unités de centimes pour n'avoir que des dizaines de centimes.

Il y a deux possibilités lorsqu'on veut éliminer des unités de centimes: soit on ramène directement à la dizaine la plus proche (28 centimes - 8), soit à la dizaine suivante (28 centimes - 18), mais avec des pièces différentes (c-à-d des pièces présentes dans le passage 28->20 ne le sont plus dans le passage 28->10), les autres possibilités ne sont pas intéressantes (on peut s'y ramener en enlevant des des dizaines par 2*5 ou 5*2 centimes)
Si on prend l'exemple de 21:
Code:

1 2 3 21 = 20 + 1 21 = 10 + 5 + 3*2
Le problème est encore présent aux étages supérieurs: dizaines de centimes, euros, dizaine d'euros.

A chaque étage il faut envisager deux possibilités (passage à la prochaine dizaine, ou à la suivante), et il y a min(5, log10(n)) étages.

Une fois qu'on est monté tout en haut: On réduit au maximum le nombre de centaines d'euros en utilisant des centaines d'euros, puis le nombre de dizaines d'euros en utilisant des 10aines d'euros, ....

Ces réductions se faisant chacune en un temps constant sur un étage, elles prennent un temps de l'ordre de min(5, log10(n)) pour tout un parcours (il y a 2^(min(5, log10(n))) parcours)
Ainsi l'algorithme prends 2^(log10(n)) * log10(n) en temps, soit n^(log10(2))*log10(n).
Ceci dans le pire des cas, il peut y avoir moins de 2^log10(n) parcours, et à partir de n = 10000, le temps n'augmente plus...

Comment réduire ??
Considérons le cas où on a un nombre x de centimes, on enlève d'abord les pièces de 5 centimes au maximum. Si on a une pièce de 1 centime en réserve, on peut toujours se ramener à un nombre pair et finir avec des pièces de 2. Sinon, si le nombre sur lequel on est est impair, on reprend une pièce de 5 (si possible) de ce qu'on a enlevé, puis on achève par pièces de 2 et pièces de 1.

Je l'ai testé, il marche à priori dans tous les cas, mais il y a sûrement moyen de réduire l'espace de stockage utilisé (par exemple avec l'allocation dynamique).

C'est une récursion de profondeur log(n), où chaque fonction invoque dans le pire des cas deux fois elle-même. (pour celles qui remontent vers les étages supérieurs)

La complexité de l'algo est max( n^(log10(2))*log10(n), 10000^(log10(2))*log10(10000) ), car à partir de n= 10000, l'algo s'exécute en un temps constant.

Dans les cas particulier de ce système monetaire (1,2,5,10,20,...) on peut optimiser l'algo que j'ai donné précédement (sortie rapide de la boucle du glouton + elaguage des branches)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
int[] solve(int[] values, int[] dispos, int remainder) {
 
	// sauvegarde de la meilleure solution
	int bestscore = Integer.MAX_VALUE;
	int[] bestsolution = null;
 
	// recherche des solutions possibles
	int[] solution = new int[values.length];
	int index = 0, score = 0;
 
	while(index>=0) {
 
		// glouton à partir de la position courante
		// avec une sortie immediate si on depasse le meilleur score
		while(index<values.length && score<bestscore) {
			solution[index]=Math.min( remainder/values[index] , dispos[index]);
			remainder-=solution[index]*values[index];
			score+=solution[index];
			index++;
		}
		index--;
 
		// c'est une meilleure solution : on la conserve.
		if (remainder==0 && score<bestscore) {
			bestscore=score;
			bestsolution=Arrays.copyOf(solution, solution.length);
		}
 
		// **** backtrack *** // 
 
		// annulation de la derniere opération effectuée
		score-=solution[index];
		remainder+=values[index]*solution[index];
		solution[index]=0;
 
		// recherche de la derniere selection non nulle
		while(index>=0 && solution[index]==0) index--;
		if (index<0) break;
 
		// decrémente la selection
		score--;
		remainder+=values[index];
		solution[index]--;
 
		// poursuit l'exploration a partir de la position suivante
		index++;
	}
 
	return bestsolution;
}

Avec l'exemple donné dans le '*.cpp' (dispo={0,1,3,0,10,10,1} et valeur=101) cela donne la solution avec 9 tours de boucle au lieu de 1176 avec mon précédant algo. :aie:

17/10/2008, 17h13
r0d

Merci beaucoup à tous pour votre aide.
J'ai testé tout ce que vous avez proposé, et suivi toutes les pistes que vous m'avez donné, mais je retombe toujours sur le même problème: ça rame trop. On travaille sur d'assez grosses sommes et on a des contraintes de temps assez dures.

Du coup je suis parti sur une autre piste, qui me permet de "jongler" avec les contraintes (en gros, ça me permet de faire les calculs à des moments où j'ai le temps): tenir à jour un tableaux de toutes les sommes que je suis capable de rendre en fonction de l'argent dont je dispose.

Encore :merci:
18/10/2008, 19h22
Zavonen

Si ça t'intéresse j'ai implémenté un automate de distributeur de boissons (virtuel) en C. Il rend la monnaie avec l'algo glouton avec backtracking.
Les sources sont à ta dispo.

Je te remercie, mais le problème c'est que la méthode que tu proposes est trop lente. Je dois calculer pour rendre la monnaie jusqu'à plus de 500€, et en plus, cet algo de résolution sera certainement utilisé lui-même dans une boucle pour des problème de gestion de BD.

Mais finalement j'ai trouvé une méthode qui semble fonctionner super bien. En tout cas c'est super rapide, et pour l'instant, je n'ai pas trouvé de faille.

Je me suis basé sur le principe que le système monétaire européen est canonique mais surtout, qu'il est structuré par le triplet 1,2,5. Je vous propose donc ma solution, en c++ (le code est affreux, c'est un brouillon. Il me reste à le mettre au propre et surtout à l'optimiser):

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <iomanip>
 
 
using namespace std;
 
// système de monnaie
vector<int> coinSystem;
 
// affiche une solution
void DisplayVector( const vector<int> & v )
{
	for ( size_t i = 0 ; i != coinSystem.size(); ++i ) 
		cout << std::setfill( ' ' ) << std::setw(5) << coinSystem[i];
	cout << endl;
	for ( size_t i = 0 ; i != v.size(); ++i ) 
		cout << std::setfill( ' ' ) << std::setw(5) << v[i];
	cout << endl;
}
 
// remet à zéro toutes les valeurs d'un vecteur à partir d'un indice donné
void ClearVector( vector<int> & v, size_t start )
{
	for ( size_t i=start; i<v.size(); ++i )
		v[i]=0;
}
 
// calcule le montant total d'un vecteur
int SumVector( const vector<int> & money )
{
	int sum = 0;
	for ( size_t i = 0; i<money.size(); ++i )
	{
		sum += money[i] * coinSystem[i];
	}
 
	return sum;
}
 
// calcule de nombre de chiffres d'un nombre
int NumDigit( int value )
{
	stringstream sst;
	sst << value;
	return (int) sst.str().size();
}
 
// algorithme glouton, à ceci près qu'on peut lui donner une solution partielle qu'il doit terminer
int SolveOne( const unsigned int value, const vector<int> & availale, vector<int> & solution, size_t start = 0 )
{
	// on met la solution à zéro, sauf la partie que l'on ne souhaite pas modifier
	ClearVector( solution, start );
 
	// on fais une copie de l'argent disponible 
	vector<int> available_copy = availale;
 
	// on calcule de reste
	int rest = value - SumVector( solution );
 
	// algo glouton
	size_t i = start;
	while ( rest > 0 && i<coinSystem.size() )
	{
		if ( rest >= coinSystem[i] )
		{
			if ( available_copy[i]>0 )
			{
				rest -= coinSystem[i];
				solution[i]++;
				available_copy[i]--;
			}
			else ++i;
		}
		else ++i;
	}
 
	return rest;
}
 
// algo de résolution
bool Solve( vector<int> & solution, const vector<int> & available, int value ) 
{
	int rest = 0;
	int start = 0;
	bool bImpossible = false;
 
	do
	{
		// on essaie de trouver une solution avec l'algo glouton
		rest = SolveOne( value, available, solution, start);
 
		// si on n'a pas trouvé de solution
		if ( rest != 0 )
		{
			// on trouve la plus petite valeur supérieure de la solution 
			int valeur = 0;
			int n = (int) coinSystem.size() - NumDigit( rest ) - 2;
			do
			{
				valeur = solution[n];
				if ( valeur == 0 ) --n;
			}
			while ( valeur == 0 && n>0 );
 
			// si on n'a pas trouvé cette valeur, c'est qu'il n'y a pas de solution
			// sinon on supprimer cette valeur à la solution et on essaie de trouver une autre solution
			// sans modifier la partie droite de notre solution partielle
			if ( n>0 )
			{
				solution[n]--;
				rest+=coinSystem[n];
				start = n+1;
			}
			else
				bImpossible = true;
		}
	}
	while ( rest > 0 && !bImpossible );
 
	return ( rest == 0 );
}
 
void FillAvailable( vector<int> & dispos )
{
	vector<int>().swap( dispos );
	dispos.push_back( 20 );	// 50 euros
	dispos.push_back( 2 );	// 20 euros
	dispos.push_back( 2 );	// 10 euros
	dispos.push_back( 5 );	// 5 euros
	dispos.push_back( 0 );	// 2 euros
	dispos.push_back( 0 );	// 1 euro
	dispos.push_back( 3 );	// 50 cts
	dispos.push_back( 2 );	// 20 cts
	dispos.push_back( 0 );	// 10 cts
	dispos.push_back( 2 );	// 5 cts
	dispos.push_back( 1 );	// 2 cts
	dispos.push_back( 0 );	// 1 ct
}
 
void FillCoinSystem( vector<int> & values )
{
	vector<int>().swap( values );
	values.push_back( 5000 );	// 50 euros
	values.push_back( 2000 );	// 20 euros
	values.push_back( 1000 );	// 10 euros
	values.push_back( 500 );	// 5 euros
	values.push_back( 200 );	// 2 euros
	values.push_back( 100 );	// 1 euro
	values.push_back( 50 );	// 50 cts
	values.push_back( 20 );	// 20 cts
	values.push_back( 10 );	// 10 cts
	values.push_back( 5 );	// 5 cts	 	
	values.push_back( 2 );	// 2 cts
	values.push_back( 1 );	// 1 ct
}
 
int main(int argc, char* argv[])
{
	vector<int> available; 
 
	FillCoinSystem( coinSystem );
	FillAvailable( available );
 
	for ( int i=1; i<50; i++ )
	{
		vector<int> solution( coinSystem.size() );
		cout << "value a devolver: " << i << endl;
 
		// resolution du problème
		bool bHaySolution = Solve( solution, available, i );
		if ( bHaySolution ) 
		{
			DisplayVector( solution);
		} 
		else 
		{
			cout << "no hay solucion" << endl;
		}
 
		if ( bHaySolution && SumVector( solution ) != i	)
		{
			cout << "error algo" << endl;
		}
	}
 
	cin.get();
	return 0;
}

edit: mouarf, je n'avais pas vu qu'il reste de l'espagnol dans le code. Avec les commentaires en français et les noms de fonctions et de variables en anglais... vive l'Europe! :aie: