Rendu de monnaie + CombinaisonS

Version imprimable

13/05/2008, 20h02
esco123

Rendu de monnaie + CombinaisonS

bonjour,
j'ai vu a travers différents forum que l'algorithme glouton est très intéressant pour résoudre un certains nombre de programme cependant j'ai un problème pour ce qui est d'obtenir toutes les combinaisons possibles...
par exemple nous avons 400e et les billets et pièces de 200 100 50 20 10, et je n'arrive pas a obtenir toutes les combinaisons...

Bonjour,

Ta question est en quelque sorte la suite du fil de bgre25.

Dans les problèmes que vous posez, il n'y a pas de contraintes sur le contenu de la "caisse" (car on a autant de billets et pièces qu'on veut : donc on peut toujours compléter par des pièces de 1€ si nécessaire, et donc il y a toujours une solution).

Tu as un montant à atteindre (par exemple : 400 €).
Et des billets ou pièces : 200 100 50 20 et 10 €.

Pour un billet de 200 : tu as trois choix : en prendre 0, 1 ou 2.
Pour un billet de 100 : tu as le choix en fonction des billets de 200 que tu as déjà choisi :
Si tu as choisi 0 billet de 200 : il te reste 400, et donc tu as 0, 1, 2, 3 ou 4 choix pour le billet de 100.
Si tu as choisi 1 billet de 200 : il te reste 200, et donc tu as 0, 1 ou 2 choix pour le billet de 100.
etc...

Donc ton algo peut être :
Code:

1 2 3 4 5 6 7 8 Considérer les billets dans l'ordre décroissant : 200, 100, 50, 20 et 10. Pour atteindre 400, pour chacun des choix possibles pour un billet de 200 : Faire ce choix de b billets. Il te reste 400 - (b * 200). Recommencer (de manière récursive) pour atteindre 400 - (b * 200) avec les billets 100, 50, 20, 10. Si tu es sur 10 (le dernier billet) : tu as l'obligation de compléter. Donc un seul choix possible.
J'espère que cela t'aidera.

13/05/2008, 21h04
esco123

je te remercie pour cette aide...je vais essayer dans la soirée pour voir ce que cela donne..et jte donne ma réponse!
13/05/2008, 23h38
Jedai

Cet algorithme va provoquer une explosion combinatoire, il faut utiliser la programmation dynamique (ou la mémoisation, son miroir) pour réduire cette explosion.

--
Jedaï

Exact, Jedai... je ne m'attendais pas à ce qu'il y a ait autant de solutions :aie:

Voici une autre proposition (en C#) :

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
 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace RenduDeMonaie
{
    class Program
    {
        static void Main( string[] args )
        {
            int somme = 400;
            int[] monaies = { 200, 100, 50, 20, 10, 5, 2, 1 };
 
            AfficherObjectif( somme, monaies );
 
            int numero = 1;
            foreach ( int[] combinaison in Combinaisons( somme, monaies ) )
            {
                AfficherSolution( numero, monaies, combinaison );
                numero++;
            }
        }
 
        static void AfficherObjectif( int somme, int[] monaies )
        {
            Console.WriteLine( "Objectif : {0}", somme );
            Console.Write( "Monaie : " );
            for ( int i = 0 ; i < monaies.Length ; i++ )
            {
                Console.Write( monaies[i] );
                Console.Write( '/' );
            }
            Console.WriteLine();
        }
 
        static void AfficherSolution( int numero, int[] monaies, int[] combinaison )
        {
            Console.Write( " >{0} : ", numero );
            for ( int i = 0 ; i < monaies.Length ; i++ )
            {
                Console.Write( combinaison[i] );
                Console.Write( "(" );
                Console.Write( monaies[i] );
                Console.Write( ")/ " );
            }
            Console.WriteLine();
        }
 
        static IEnumerable<int[]> Combinaisons( int somme, int[] monaies )
        {
            int positionUnite = monaies.Length - 1;
 
            int[] cumuls = new int[monaies.Length];
            int[] valeurs = new int[monaies.Length];
 
            cumuls.Initialize();
            valeurs.Initialize();
 
            bool continuer = true;
 
            while ( continuer )
            {
                valeurs[positionUnite] = somme - (cumuls[positionUnite - 1] / monaies[positionUnite]);
                cumuls[positionUnite] = cumuls[positionUnite - 1] + (valeurs[positionUnite] * monaies[positionUnite]);
 
                if ( cumuls[positionUnite] == somme )
                    yield return valeurs;
 
                continuer = Suivant( valeurs, cumuls, monaies, somme, positionUnite );
            }
        }
 
        static bool Suivant( int[] valeurs, int[] cumuls, int[] monaies, int somme, int positionUnite )
        {
            int index = positionUnite - 1;
 
            while ( index >= 0 )
            {
                valeurs[index]++;
                cumuls[index] = (index == 0 ? 0 : cumuls[index - 1]) + valeurs[index] * monaies[index];
 
                if ( cumuls[index] > somme )
                {
                    cumuls[index] = 0;
                    valeurs[index] = 0;
                    index--;
                }
                else
                    return true;
            }
 
            return false;
        }
    }
}

14/05/2008, 23h40
pseudocode

@Alikendarfen: J'ai essayé de suivre ton code mais je me suis perdu :aie:. Tu as mis une relation d'ordre sur les solutions, c'est ca ?
15/05/2008, 03h06
Jedai

Je rappelle un vieux sujet sur la question, où les solutions avaient été pas trop mal explorées.

--
Jedaï
15/05/2008, 06h39
Alikendarfen
Citation:

Envoyé par pseudocode

@Alikendarfen: J'ai essayé de suivre ton code mais je me suis perdu :aie:. Tu as mis une relation d'ordre sur les solutions, c'est ca ?

...pas réellement.

on a trois tableaux : les valeurs courantes explorées, le cumul courant pour ces valeurs, ceci en vis à vis de la table des monnaies.

objectif (somme) = 400
Code:

1 2 3 4 monnaies : 200 100 50 20 10 5 2 1 valeurs : [ 0 2 1 4 0 2 1 ] 58 cumuls : 0 200 250 330 330 340 342 400
La fonction "Suivant" parcourt toutes les combinaisons possibles pour les valeurs entre crochets ci-dessus, en regardant qu'on ne dépasse par l'objectif (à l'aide du cumul).
Et on complète sur "l'unité", en vérifiant que ça colle à l'objectif (si l'unité n'était pas '1', on n'aurait pas toujours une solution juste).

D'autres idées pour ce problème ?
15/05/2008, 09h14
Jedai

Ton code contient une erreur, les résultats sont incorrects.

--
Jedaï

Ben décidément... :oops::oops:

Il manquait un morceau :

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
 
static bool Suivant( int[] valeurs, int[] cumuls, int[] monaies, int somme, int positionUnite )
        {
            int index = positionUnite - 1;
 
            while ( index >= 0 )
            {
                valeurs[index]++;
                cumuls[index] = (index == 0 ? 0 : cumuls[index - 1]) + valeurs[index] * monaies[index];
 
                if ( cumuls[index] > somme )
                {
                    cumuls[index] = 0;
                    valeurs[index] = 0;
                    index--;
                }
                else
                {
// ICI :
                    for ( int i = index + 1 ; i < positionUnite ; i++ )
                        cumuls[i] = cumuls[index];
                    return true;
                }
            }
 
            return false;
        }

18/05/2008, 18h05
benDelphic

il suffisait de résoudre le problème de sac a dos associé non , et l' algorithme glouton tient en 3 lignes maximum 8O
18/05/2008, 23h39
Jedai

Citation:

Envoyé par benDelphic

il suffisait de résoudre le problème de sac a dos associé non , et l' algorithme glouton tient en 3 lignes maximum 8O

On a dit "obtenir toutes les combinaisons possibles", pas obtenir n'importe quelle solution...

--
Jedaï
19/05/2008, 16h41
benDelphic

Citation:

Envoyé par Jedai

On a dit "obtenir toutes les combinaisons possibles", pas obtenir n'importe quelle solution...

--
Jedaï

ben la il suffit de varier le cout ,:yaisse2: