Предположим, у меня есть 4 монеты номиналов 1 3 4 5. Я хочу сделать это 7. Я узнаю, как найти, как много возможных способов сделать. Но я хочу определить, какое минимальное количество монет необходимо использовать для этого. Пример: 5 + 1 + 1 = 7 снова 3 + 4 = 7. Таким образом, минимальное количество монет равно 2. Любой псевдокод или пояснение или исходный код будут полезныПроблемы с монетами
ответ
Если вы хотите внести изменения для числа n, настройте массив number_of_coins [n] и заполните его слева направо правильно. number_of_coins [0] - 0, очевидно. Следующие несколько вы можете сделать вручную (хотя, как только у вас будет алгоритм, он автоматически заполнит их). Чтобы заполнить большие записи m в массиве, подумайте об этом: что, если я удалю 1 цент из m? Или 3 цента? Или 4 цента? Или 5 центов?
Как только у вас будет количество монет до n, вы можете пройти назад, чтобы найти точные монеты.
Я возьму на него удар. Я думаю, вы должны определить вектор ваших номиналов:
vector<int> denominations {1,3,5,7};
оттуда, написать рекурсивную функцию, которая принимает в номиналах, а также сумму, чтобы сделать из номиналов:
int recursive_totals(const vector<int> denominations, int amount_to_make);
эта функция вернет 0, если amount_to_make
меньше или равно 0, в противном случае он бы проходное номиналов:
int sum_totals = 0;
for (int denom : denominations)
{
if (amount_to_make - denom == 0)
sum_totals+=1;
else
sum_totals+=recursive_totals(denominations, amount_to_make - denom);
}
это грубый код и может нужно настроить, но я думаю, что здесь работает рекурсивная функция. Непосредственная проблема, которую я вижу, заключается в том, что порядок не будет иметь значения, как я написал его здесь, и вы можете получить дубликаты, но есть способ обойти это.
EDIT: Я получил его работу, но не буду размещать здесь код. Этот метод работает, и если вы решите попробовать его, не стесняйтесь задавать любые вопросы, которые вам нужны, и я постараюсь помочь.
сайт dosen't работает как этот ^. вы должны сказать нам, что вы сделали/написано/исследовано, и если вы застряли в какой-то момент, SO поможет. –
@AbhinavGauniyal Неправильно. SO не должен быть свободным решением для домашних заданий. Но на самом деле, по какой-то странной причине, он работает так все время. (См. Ответы ниже. – Drop
Вопросы, требующие помощи, должны включать в себя то, что вы пробовали, и какие результаты вы получаете, или они будут закрыты как вне темы. – ssube