Discussion :

[esco123]

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

[Alikendarfen]

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 :

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

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.

[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!

[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ï

[Alikendarfen]

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

Voici une autre proposition (en C#) :

Code C# :

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
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;
        }
    }
}

[pseudocode]

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