1. #1
    Membre actif Avatar de DarkSeiryu
    Homme Profil pro
    Développeur Web
    Inscrit en
    janvier 2009
    Messages
    425
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 28
    Localisation : France, Haute Savoie (Rhône Alpes)

    Informations professionnelles :
    Activité : Développeur Web

    Informations forums :
    Inscription : janvier 2009
    Messages : 425
    Points : 275
    Points
    275

    Par défaut Algo de rendu de monnaie (oui, encore un)

    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.

  2. #2
    Responsable Qt


    Avatar de dourouc05
    Homme Profil pro
    Doctorant
    Inscrit en
    août 2008
    Messages
    21 837
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : Doctorant
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 21 837
    Points : 112 939
    Points
    112 939

    Par défaut



    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 ?
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions) ? Contactez-moi par MP.

    Nouveau ! Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  3. #3
    Membre actif Avatar de DarkSeiryu
    Homme Profil pro
    Développeur Web
    Inscrit en
    janvier 2009
    Messages
    425
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 28
    Localisation : France, Haute Savoie (Rhône Alpes)

    Informations professionnelles :
    Activité : Développeur Web

    Informations forums :
    Inscription : janvier 2009
    Messages : 425
    Points : 275
    Points
    275

    Par défaut

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

  4. #4
    Membre régulier
    Homme Profil pro
    Inscrit en
    octobre 2013
    Messages
    63
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : octobre 2013
    Messages : 63
    Points : 122
    Points
    122

    Par défaut

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

  5. #5
    Membre actif Avatar de DarkSeiryu
    Homme Profil pro
    Développeur Web
    Inscrit en
    janvier 2009
    Messages
    425
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 28
    Localisation : France, Haute Savoie (Rhône Alpes)

    Informations professionnelles :
    Activité : Développeur Web

    Informations forums :
    Inscription : janvier 2009
    Messages : 425
    Points : 275
    Points
    275

    Par défaut

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

  6. #6
    Expert éminent
    Homme Profil pro
    Développeur Freelance
    Inscrit en
    janvier 2009
    Messages
    3 116
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France

    Informations professionnelles :
    Activité : Développeur Freelance

    Informations forums :
    Inscription : janvier 2009
    Messages : 3 116
    Points : 6 400
    Points
    6 400

    Par défaut

    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.

  7. #7
    Membre régulier
    Homme Profil pro
    Inscrit en
    octobre 2013
    Messages
    63
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : octobre 2013
    Messages : 63
    Points : 122
    Points
    122

    Par défaut

    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

  8. #8
    Membre régulier
    Homme Profil pro
    Inscrit en
    octobre 2013
    Messages
    63
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : octobre 2013
    Messages : 63
    Points : 122
    Points
    122

    Par défaut

    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!

  9. #9
    Membre actif Avatar de DarkSeiryu
    Homme Profil pro
    Développeur Web
    Inscrit en
    janvier 2009
    Messages
    425
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 28
    Localisation : France, Haute Savoie (Rhône Alpes)

    Informations professionnelles :
    Activité : Développeur Web

    Informations forums :
    Inscription : janvier 2009
    Messages : 425
    Points : 275
    Points
    275

    Par défaut

    Citation Envoyé par tatayo Voir le message
    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.
    Citation Envoyé par kija13 Voir le message
    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. #10
    Membre éprouvé Avatar de 10_GOTO_10
    Profil pro
    Inscrit en
    juillet 2004
    Messages
    802
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : juillet 2004
    Messages : 802
    Points : 1 182
    Points
    1 182

    Par défaut

    Citation Envoyé par tatayo Voir le message
    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
    Sondages gratuits : Le troc d'opinions

  11. #11
    Membre actif Avatar de DarkSeiryu
    Homme Profil pro
    Développeur Web
    Inscrit en
    janvier 2009
    Messages
    425
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 28
    Localisation : France, Haute Savoie (Rhône Alpes)

    Informations professionnelles :
    Activité : Développeur Web

    Informations forums :
    Inscription : janvier 2009
    Messages : 425
    Points : 275
    Points
    275

    Par défaut

    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

  12. #12
    Rédacteur/Modérateur
    Avatar de Trap D
    Profil pro
    Inscrit en
    septembre 2003
    Messages
    4 778
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : septembre 2003
    Messages : 4 778
    Points : 6 162
    Points
    6 162

    Par défaut

    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).
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : Intérieur avec jeune femme de Vilhelm Hammershoi

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Algo rendu de monnaie
    Par Matt_NewDev dans le forum Général Algorithmique
    Réponses: 6
    Dernier message: 28/03/2012, 17h24
  2. [apache][.htaccess]Oui encore un....
    Par sanosuke85 dans le forum Apache
    Réponses: 3
    Dernier message: 15/05/2006, 19h41
  3. Preloader, et oui encore un !
    Par rawkus dans le forum ActionScript 1 & ActionScript 2
    Réponses: 10
    Dernier message: 09/05/2006, 13h06
  4. Et oui encore un probleme d'icone dans une Jframe
    Par frett dans le forum AWT/SWING
    Réponses: 7
    Dernier message: 17/02/2006, 15h12
  5. Drivers ODBC, ADO et IB (et oui encore!! )
    Par lio33 dans le forum Débuter
    Réponses: 1
    Dernier message: 14/09/2005, 09h51

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo