Manual clasa a Xi a |
Tehnici de programare |
Microproiecte |
Rezolvaţi problema plăţii unei sume cu bancnote cu valori date, pentru fiecare valoare de bancnotă având la dispoziţie un anumit număr de bancnote, folosind metoda programării dinamice şi metoda backtracking .
# include < iostream >
# include < cstring >
using namespace std ;
const int MAX_SUM = 1000 ;
const int MAX_DENOMINATIONS = 10 ;
int dp [MAX_SUM+ 1 ];
int denominations [MAX_DENOMINATIONS];
int counts [MAX_DENOMINATIONS];
int main () {
int numDenominations , targetSum ;
cin >> numDenominations >> targetSum ;
for ( int i = 0 ; i < numDenominations ; i++) {
cin >> denominations [i] >> counts [i];
}
memset ( dp , -1 , sizeof ( dp ));
dp [ 0 ] = 0 ;
for ( int i = 0 ; i < numDenominations ; i++) {
for ( int j = 0 ; j <= targetSum ; j++) {
if ( dp [j] != -1 ) {
int count = 1 ;
while ( count <= counts [i] && j + count * denominations [i] <= targetSum ) {
int newSum = j + count * denominations [i];
if ( dp [ newSum ] == -1 || dp [ newSum ] > dp [j] + count ) {
dp [ newSum ] = dp [j] + count ;
}
count ++;
}
}
}
}
cout << " Numar minim de bancnote necesare: " << dp [ targetSum ] << endl ;
return 0 ;
}
# include < iostream >
# include < climits >
using namespace std ;
const int MAX_DENOMINATIONS = 10 ;
int denominations [MAX_DENOMINATIONS];
int counts [MAX_DENOMINATIONS];
int numDenominations , targetSum ;
int minBanknotes = INT_MAX;
void backtrack ( int index, int remainingSum , int banknotesUsed ) {
if ( remainingSum == 0 ) {
minBanknotes = min ( minBanknotes , banknotesUsed );
return ;
}
if (index == numDenominations || remainingSum < 0 ) {
return ;
}
for ( int i = 0 ; i <= counts [index]; i++) {
if ( remainingSum - denominations [index] * i >= 0 ) {
backtrack (index + 1 , remainingSum - denominations [index] * i, banknotesUsed + i);
} else {
break ;
}
}
}
int main () {
cin >> numDenominations >> targetSum ;
for ( int i = 0 ; i < numDenominations ; i++) {
cin >> denominations [i] >> counts [i];
}
backtrack ( 0 , targetSum , 0 );
if ( minBanknotes != INT_MAX) {
cout << " Numar minim de bancnote necesare: " << minBanknotes << endl ;
} else {
cout << "Nu se poate realiza suma dorita" << endl ;
}
return 0 ;
}
Pentru a rula aceste programe, trebuie să introduci numărul de denominații, suma țintă, apoi pentru fiecare denominație să introduci valoarea și numărul de bancnote disponibile. Programele vor afișa numărul minim de bancnote necesare pentru a plăti suma țintă.
De exemplu, pentru a rula programul cu 3 denominații de bancnote - 1, 5 și 10, având 5 bancnote de 1, 2 de 5 și 1 de 10, și dorești să plătești suma de 18, intrările ar arăta astfel:
3 18
1 5
5 2
10 1
Output- ul programului ar fi:
Numar minim de bancnote necesare: 4
Aceasta înseamnă că poți plăti suma de 18 folosind 4 bancnote (de exemplu, 1 bancnotă de 10, 1 bancnotă de 5 și 2 bancnote de 1).
Atât implementarea cu programare dinamică, cât și cea cu backtracking vor oferi același rezultat, dar folosesc abordări diferite pentru a rezolva problema. Programarea dinamică este de obicei mai rapidă, dar poate necesita mai multă memorie, în timp ce backtracking-ul explorează toate soluțiile posibile și poate fi mai lent, dar necesită mai puțină memorie.