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