# include < iostream >
using namespace std ;
const int MAX_BANCNOTE = 100 ;
void backtracking ( int suma, int valori_bancnote [], int sol[], int min_sol [], int index, int nr_bancnote , int n) {
if (suma == 0 ) {
if ( nr_bancnote < min_sol [ 0 ]) {
min_sol [ 0 ] = nr_bancnote ;
for ( int i = 0 ; i < n; ++i) {
min_sol [i + 1 ] = sol[i];
}
}
return ;
}
if (index >= n) {
return ;
}
int max_bancnote = suma / valori_bancnote [index];
for ( int i = 0 ; i <= max_bancnote ; ++i) {
sol[index] = i;
backtracking (suma - i * valori_bancnote [index], valori_bancnote , sol, min_sol , index + 1 , nr_bancnote + i, n);
}
}
int main () {
int suma, n;
cout << " Introduceti suma: " ;
cin >> suma;
cout << " Introduceti numarul de bancnote: " ;
cin >> n;
int valori_bancnote [MAX_BANCNOTE];
cout << " Introduceti valorile bancnotelor: " ;
for ( int i = 0 ; i < n; ++i) {
cin >> valori_bancnote [i];
}
int sol[MAX_BANCNOTE] = { 0 };
int min_sol [MAX_BANCNOTE + 1 ];
min_sol [ 0 ] = INT_MAX;
backtracking (suma, valori_bancnote , sol, min_sol , 0 , 0 , n);
if ( min_sol [ 0 ] == INT_MAX) {
cout << "Nu se poate plati suma cu bancnotele disponibile." << endl ;
} else {
cout << "Modalitatea de plata cu numar minim de bancnote este: " << endl ;
for ( int i = 0 ; i < n; ++i) {
cout << valori_bancnote [i] << ": " << min_sol [i + 1 ] << endl ;
}
}
return 0 ;
}
Acest program utilizează backtracking pentru a găsi modalitatea de plată a unei sume cu un număr minim de bancnote, având la dispoziție un număr nelimitat de bancnote pentru fiecare valoare. Acesta afișează modalitatea de plată sau un mesaj în cazul în care suma nu poate fi plătită cu bancnotele disponibile.
# include < iostream >
# include <vector>
using namespace std ;
void backtracking ( int suma, const vector< int > & valori_bancnote , vector< int > &sol, vector< int > & min_sol , int index, int nr_bancnote ) {
if (suma == 0 ) {
if ( nr_bancnote < min_sol. size ()) {
min_sol = sol;
}
return ;
}
if (index >= valori_bancnote. size ()) {
return ;
}
int max_bancnote = suma / valori_bancnote [index];
for ( int i = 0 ; i <= max_bancnote ; ++i) {
sol[index] = i;
backtracking (suma - i * valori_bancnote [index], valori_bancnote , sol, min_sol , index + 1 , nr_bancnote + i);
}
}
int main () {
int suma, n;
cout << " Introduceti suma: " ;
cin >> suma;
cout << " Introduceti numarul de bancnote: " ;
cin >> n;
vector< int > valori_bancnote (n) ;
cout << " Introduceti valorile bancnotelor: " ;
for ( int i = 0 ; i < n; ++i) {
cin >> valori_bancnote [i];
}
vector< int > sol (n, 0 ) ;
vector< int > min_sol (n, INT_MAX) ;
backtracking (suma, valori_bancnote , sol, min_sol , 0 , 0 );
if ( min_sol. size () == n && min_sol [ 0 ] == INT_MAX) {
cout << "Nu se poate plati suma cu bancnotele disponibile." << endl ;
} else {
cout << "Modalitatea de plata cu numar minim de bancnote este: " << endl ;
for ( int i = 0 ; i < n; ++i) {
cout << valori_bancnote [i] << ": " << min_sol [i] << endl ;
}
}
return 0 ;
}