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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
| #include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <iomanip>
using namespace std;
// système de monnaie
vector<int> coinSystem;
// affiche une solution
void DisplayVector( const vector<int> & v )
{
for ( size_t i = 0 ; i != coinSystem.size(); ++i )
cout << std::setfill( ' ' ) << std::setw(5) << coinSystem[i];
cout << endl;
for ( size_t i = 0 ; i != v.size(); ++i )
cout << std::setfill( ' ' ) << std::setw(5) << v[i];
cout << endl;
}
// remet à zéro toutes les valeurs d'un vecteur à partir d'un indice donné
void ClearVector( vector<int> & v, size_t start )
{
for ( size_t i=start; i<v.size(); ++i )
v[i]=0;
}
// calcule le montant total d'un vecteur
int SumVector( const vector<int> & money )
{
int sum = 0;
for ( size_t i = 0; i<money.size(); ++i )
{
sum += money[i] * coinSystem[i];
}
return sum;
}
// calcule de nombre de chiffres d'un nombre
int NumDigit( int value )
{
stringstream sst;
sst << value;
return (int) sst.str().size();
}
// algorithme glouton, à ceci près qu'on peut lui donner une solution partielle qu'il doit terminer
int SolveOne( const unsigned int value, const vector<int> & availale, vector<int> & solution, size_t start = 0 )
{
// on met la solution à zéro, sauf la partie que l'on ne souhaite pas modifier
ClearVector( solution, start );
// on fais une copie de l'argent disponible
vector<int> available_copy = availale;
// on calcule de reste
int rest = value - SumVector( solution );
// algo glouton
size_t i = start;
while ( rest > 0 && i<coinSystem.size() )
{
if ( rest >= coinSystem[i] )
{
if ( available_copy[i]>0 )
{
rest -= coinSystem[i];
solution[i]++;
available_copy[i]--;
}
else ++i;
}
else ++i;
}
return rest;
}
// algo de résolution
bool Solve( vector<int> & solution, const vector<int> & available, int value )
{
int rest = 0;
int start = 0;
bool bImpossible = false;
do
{
// on essaie de trouver une solution avec l'algo glouton
rest = SolveOne( value, available, solution, start);
// si on n'a pas trouvé de solution
if ( rest != 0 )
{
// on trouve la plus petite valeur supérieure de la solution
int valeur = 0;
int n = (int) coinSystem.size() - NumDigit( rest ) - 2;
do
{
valeur = solution[n];
if ( valeur == 0 ) --n;
}
while ( valeur == 0 && n>0 );
// si on n'a pas trouvé cette valeur, c'est qu'il n'y a pas de solution
// sinon on supprimer cette valeur à la solution et on essaie de trouver une autre solution
// sans modifier la partie droite de notre solution partielle
if ( n>0 )
{
solution[n]--;
rest+=coinSystem[n];
start = n+1;
}
else
bImpossible = true;
}
}
while ( rest > 0 && !bImpossible );
return ( rest == 0 );
}
void FillAvailable( vector<int> & dispos )
{
vector<int>().swap( dispos );
dispos.push_back( 20 ); // 50 euros
dispos.push_back( 2 ); // 20 euros
dispos.push_back( 2 ); // 10 euros
dispos.push_back( 5 ); // 5 euros
dispos.push_back( 0 ); // 2 euros
dispos.push_back( 0 ); // 1 euro
dispos.push_back( 3 ); // 50 cts
dispos.push_back( 2 ); // 20 cts
dispos.push_back( 0 ); // 10 cts
dispos.push_back( 2 ); // 5 cts
dispos.push_back( 1 ); // 2 cts
dispos.push_back( 0 ); // 1 ct
}
void FillCoinSystem( vector<int> & values )
{
vector<int>().swap( values );
values.push_back( 5000 ); // 50 euros
values.push_back( 2000 ); // 20 euros
values.push_back( 1000 ); // 10 euros
values.push_back( 500 ); // 5 euros
values.push_back( 200 ); // 2 euros
values.push_back( 100 ); // 1 euro
values.push_back( 50 ); // 50 cts
values.push_back( 20 ); // 20 cts
values.push_back( 10 ); // 10 cts
values.push_back( 5 ); // 5 cts
values.push_back( 2 ); // 2 cts
values.push_back( 1 ); // 1 ct
}
int main(int argc, char* argv[])
{
vector<int> available;
FillCoinSystem( coinSystem );
FillAvailable( available );
for ( int i=1; i<50; i++ )
{
vector<int> solution( coinSystem.size() );
cout << "value a devolver: " << i << endl;
// resolution du problème
bool bHaySolution = Solve( solution, available, i );
if ( bHaySolution )
{
DisplayVector( solution);
}
else
{
cout << "no hay solucion" << endl;
}
if ( bHaySolution && SumVector( solution ) != i )
{
cout << "error algo" << endl;
}
}
cin.get();
return 0;
} |
Envoyé par méphistopheles
Serais-il possible de le traduire légerement en langage algo ?
Répondre avec citation
Partager