Discussion :

[DarkSeiryu]

Bonjour,

Je commence directement par calmer ceux qui vont crier au scandale là-dessus : ouais j'ai cherché sur le forum. Et j'ai cherché un moment aussi sur le net, pour trouver des algo gloutons et de la programmtion dynamique.
Cependant, j'ai un cas un peu différent ou du moins, je n'arrive pas à retranscrire ce que j'ai trouvé pour gérer ce cas.

Comme pour toutes les personnes qui ont eu à faire cet exo, le but est donc de simuler un rendu de monnaie, en ayant un nombre de pièces limité.
TODO :

1. Faire un rendu de monnaie avec un minimum de pièces (optimal quoi, genre pour 2.50€, une pièce de 2 et une de 0.50)
2. Faire un rendu de monnaie avec un maximum de pièces (ex pour 2.50€ : 4x0.01 + 3x0.02 + 4x0.10 + 5x0.20 + 2x0.50 )

Le 1er est OK, même si j'avais fait ni gloutonnerie ni DP, j'm'en suis sorti.
Mais pour le 2ème, j'sais juste pas par quoi commencer.

Pour les codeurs Java : https://github.com/MickaelBenes/coin...exec/Main.java

Je suppose que la soluce (pour le minimum, le maximum fonctionne juste pas) n'est pas optimale mais bon ça fonctionne. Après j'ai trouvé ça :

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
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
public static void main( String[] args ) {
		// INPUT: valeurs et nombre de pieces disponibles
		int[] values = new int[] { 200, 100, 50, 20, 10, 5, 2, 1 };
		int[] dispos = new int[] { 0, 0, 10, 10, 0, 0, 0, 10 };
 
		// 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");
		}
	}
 
	public static 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;
	}

Qui du coup lui est optimal, mais ne me permet d'effectuer que le premier cas.

Comment faire pour le deuxième ?

Merci.

[dourouc05]

J'aurais tendance à dire que le problème de maximisation est simple : que des pièces d'un centime. Ou il y a des contraintes qui rendent le problème intéressant ?

[DarkSeiryu]

Merci pour la réponse.

Ouais j'aurais aimé que ce soit aussi simple (pas vraiment, ça n'a rien d'intéressant comme ça) mais les pièces sont limitées (comme indiqué dans mon premier post).

[kija13]

Bonjour

Une idée :
à partir d'une solution quelconque on prend la pièce de valeur maxi de la solution et on cherche si on peut la remplacer avec des pièces encore disponibles.
Si c’est possible on le fait et on boucle, sinon on passe à une pièce de valeur plus faible...

[DarkSeiryu]

Le problème étant que ça me ferait faire ce traitement n fois jusqu'à trouver la solution qui me retourne le plus de pièces possibles en fonction des pièces disponibles, vu que je partirais du plus grand au plus petit. Pas super opti nan ?

J'ai vu qu'il y a possibilité de faire une fonction retournant le nombre de manières existantes pour arriver au résultat donné (Dynamic Programing). Du coup à partir de là il doit y avoir moyen de retourner la solution optimale (avec un minimum de pièces) et la plus "nase" (avec un maximum de pièces). Mais c'est justement là que j'me perds...

[tatayo]

Bonjour,
Comment ferais-tu en vrai ?
Tu commencerais par prendre les plus petites pièces, jusqu'à atteindre le montant à rendre.
S'il n'y a pas assez de pièce, tu passes au pièces supérieures, et tu recommences.
Au final, un cas peut se produire: tu as dépassé le montant à rendre.
Il faut repartir dans l'autre sens, et appliquer au montant "trop rendu" l'algorithme "optimal", en tapant dans les pièces utilisées (pour en reprendre le moins possible).

Tatayo.

[kija13]

Savoir le nombre de solutions possibles ne t'en donne en fait aucune en détails...
Imagine une méthode "à la main".
En centimes tu as comme pièces 100,100,50,50,20,20,10,5,2,2,2,2,1,1,1,1.
Et la somme est 140.
Comment fais-tu?
A partir de la solution évidente 100,20,20 comment optimises-tu?
Avec ma méthode tu obtiens
50,50,20,20
50,50,20,10,5,2,2,1
50,50,20,10,2,2,2,2,1,1
50,50,20,10,2,2,2,1,1,1,1
sauf erreur

[kija13]

Bonne méthode de tatayo!
une 1e étape simple qui aboutira presque toujours à une somme trop grande mais
une 2e étape qui utilise justement l'algo optimal!

[DarkSeiryu]

Bonjour,
Comment ferais-tu en vrai ?
Tu commencerais par prendre les plus petites pièces, jusqu'à atteindre le montant à rendre.
S'il n'y a pas assez de pièce, tu passes au pièces supérieures, et tu recommences.
Au final, un cas peut se produire: tu as dépassé le montant à rendre.
Il faut repartir dans l'autre sens, et appliquer au montant "trop rendu" l'algorithme "optimal", en tapant dans les pièces utilisées (pour en reprendre le moins possible).

Tatayo.

Bonne méthode de tatayo!
une 1e étape simple qui aboutira presque toujours à une somme trop grande mais
une 2e étape qui utilise justement l'algo optimal!

Effectivement, faire ça en deux fois sans trop de prendre la tête, pas con ! J'essaie ça ce soir.

Merci à vous deux !

[10_GOTO_10]

Bonjour,
Comment ferais-tu en vrai ?
Tu commencerais par prendre les plus petites pièces, jusqu'à atteindre le montant à rendre.
S'il n'y a pas assez de pièce, tu passes au pièces supérieures, et tu recommences.
Au final, un cas peut se produire: tu as dépassé le montant à rendre.
Il faut repartir dans l'autre sens, et appliquer au montant "trop rendu" l'algorithme "optimal", en tapant dans les pièces utilisées (pour en reprendre le moins possible).

Tatayo.

Pour avoir la solution optimale, il faut prendre la totalité les pièces dans l'étape 1. Sinon, on risque de ne pas avoir la meilleure solution.

Exemple :
Pièces disponibles : 20 pièces de 1, 3 pièces de 20, une pièce de 50
Somme à payer : 70

Selon ton système :
On donne 20 x 1, et 3 x 20 et on arrête là puisque la somme dépasse, puis à l'étape 2 on rend 10 x 1 => il reste 13 pièces

Si on prend la totalité:
On a 130, il faut donc rendre 60. on peut rendre 3 x 20 (solution optimale selon les pièces disponibles) => il reste 21 pièces

[DarkSeiryu]

Salut !

Du coup voilà ça fonctionne !
J'ai fait comme tatayo l'a suggéré, ça marche niquel.

@GOTO : t'avais raison fallait bien reprendre toutes les pièces dispo à la base, sinon forcément le résultat n'aurait pas été bon.

Merci à tous !

PS : pour les curieux : https://github.com/MickaelBenes/coin-change

[Trap D]

Je viens de voir cette discussion, un peu tard c'est vrai, mais c'est un problème de contraintes qui se résoud très simplement en Prolog, (et dans tout autre langage ayant une bibliothèque de gestion de contraintes) :

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
:- use_module(library(clpfd)).
:- use_module(library(lambda)).
 
rendu(S, L1, L2) :-
	length(L1, 9),
	L1 ins 0..100,
	length(L2, 9),
	L2 ins 0..100,
	Pieces =      [1  ,  2,  5, 10, 20, 50, 100, 200, 500],
	Disponibles = [100, 50, 70, 50, 30, 80,  45, 100,  70],
	maplist(\X^Y^Z^(X #=< Z, Y #=< Z), L1, L2, Disponibles),
	foldl(\X^Y^Z^T^(T #= Z+X*Y), L1, Pieces, 0, S),
	foldl(\X^Y^Z^(Z #= X+Y), L1, 0, S1),
	foldl(\X^Y^Z^T^(T #= Z+X*Y), L2, Pieces, 0, S),
	foldl(\X^Y^Z^(Z #= X+Y), L2, 0, S2),
	labeling([ff,min(S1)], L1),
	labeling([ff,max(S2)], L2).

L1 contient le rendu avec le minimum de pièces, L2 avec le maximum de pieces :

?- rendu(250, L1, L2).
L1 = [0,0,0,0,0,1,0,1,0],
L2 = [100,50,10,0,0,0,0,0,0] .

(Du au fait que la librairie fonctionne avec des entiers on donne 250 au lieu de 2,50).