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