un algo pour rendre la monnaie

**r0d** · 18/09/2008, 17h09

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:

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

**khayyam90** · 18/09/2008, 17h45

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.

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.

**SpiceGuid** · 18/09/2008, 18h41

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€,...

**r0d** · 18/09/2008, 18h58

@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

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

**plegat** · 18/09/2008, 19h27

Salut,

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?

**r0d** · 18/09/2008, 19h56

Envoyé par plegat

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

ou je me suis trompé

mais je ne crois pas:

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

**plegat** · 18/09/2008, 22h57

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

Au temps pour moins, je viens de piger ton contre-exemple!

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

**Furikawari** · 19/09/2008, 10h01

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

**pseudocode** · 19/09/2008, 10h16

Glouton avec backtracking

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

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 java :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

**Jedai** · 19/09/2008, 20h38

Une solution en Haskell :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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ï

**pseudocode** · 18/09/2008, 20h12

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.

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.

un algo pour rendre la monnaie

Algorithmes et structures de données

Vue hybride

Discussions similaires

Partager

Partager