Given a certain amount and a given number of notes along with their available quantities find out the number of maximum notes you can give to the user
Example:
Notes {{100,10}, {500, 5}, {1000, 2}, {2000, 1}};
(Here the first value is the denomination of the note and the second value is the number of notes of that type that are available with us.)
Amount = 1000, Answer = 10
Amount = 1100, Answer = 7 (6 * 100 + 1 * 500)
This is something that I have been trying but I feel something is missing still
int maxNotes(int amount, vector<pair<int, int>>& notes) {
if (amount == 0) {
return 0;
}
if (amount < 0) {
return INT_MIN;
}
int ans = INT_MIN;
int smallestAmount = 0;
for (int i = 0 ; i < notes.size(); i++) {
if (notes[i].second > 0) {
smallestAmount = notes[i].first;
break;
}
}
for (int i = smallestAmount; i <= amount; i+= smallestAmount) {
for (int j = 0; j < notes.size(); j++) {
if (notes[j].second <= 0) {
continue;
}
int temp = INT_MIN;
for (int k = 1; k <= notes[j].second; k++) {
if (amount < notes[j].second*k) {
continue;
}
if (k > notes[j].second) {
continue;
}
notes[j].second -= k;
int temp2 = k + maxNotes(amount - k * notes[j].first, notes);
temp = max(temp, temp2);
notes[j].second += k;
}
ans = max(ans, temp);
}
}
return ans;
}Comments (0)