Описание проблемы:
В Англии валюта состоит из фунта, фунтов стерлингов и пенсов, р и
Всего в обращении восемь монет:
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
Сделать £ 2 можно следующим образом:
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
Сколько можно заработать £ 2, используя любое количество монет?
Я попытался придумать собственный алгоритм для этого и потерпел неудачу. Итак, я наткнулся на этот (принятый ответ). Я попытался повторить это в C ++ здесь. Когда я ввожу 1, 2 и 5 в combos () в функции main (), он дает правильный ответ, но 10 возвращает 11, когда должно быть 12. Что не так с моим алгоритмом?
#include <iostream>
#include <cstdlib>
using namespace std;
int coin[] = {1, 2, 5, 10, 20, 50, 100, 200};
/*Amounts entered must be in pence.*/
int combinations(int amount, int size) {
int comboCount = 0;
if(amount > 0) {
if(size >= 0 && amount >= coin[size])
comboCount += combinations(amount - coin[size], size);
if(size > 0) //don't do if size is 0
comboCount += combinations(amount, size-1);
} else if(amount == 0)
comboCount++;
return comboCount;
}
int combos(int amount) {
int i = 0;
//get largest coin that fits
for(i = 7; coin[i] > amount && i >= 0; i--);
return combinations(amount, i);
}
int main() {
cout << "Answer: " << combos(10) << endl;
return 0;
}