Комбинации с монеток

В копилке есть монетки следующих номиналов:
1 2 5 10 25 50 100
из копилки достаются К монеток
Сколько различных значений может иметь сумма полученных денег?

Пример:
Ввод:
2 10 25 3
2 - количество номиналов (далее 10 и 25), которые есть в копилке
3 - количество вытянутых монеток
Вывод:
4
10 + 10 + 10 = 30 ;
10 + 10 + 25 = 45;
10 + 25 + 25 = 60;
25 + 25 + 25 = 75;
Итого, 4 разных значения

Ввод:
4 1 2 5 10 3
Вывод: 19

0

спасибо, ознакомился.

0

Вообще-то количество разных вариантов можно посчитать за формулой
но как узнать количество разных сум, как перебрать все возможные варианты сум?

0

Сообщение от Darky спасибо, ознакомился.

пожалуйста, вот ещё

0

Mayonez, Какие ограничения К, кол-во номиналов и максимальный номинал?

1

количество номиналов 7:
1____2____5____10____25____50_____100
максимальный номинал 100
К меньше 1000
и вводится в конце

0

Количество номиналов не более 7? В приведенных ранее двух примерах кол-во номиналов было 2 и 4. А по времени есть ограничения?

1

Сообщение от valeriikozlov Количество номиналов не более 7?

да

Сообщение от valeriikozlov А по времени есть ограничения?

нет

0

Сообщение от Mayonez Ввод: 4 1 2 5 10 3 Вывод: 19

Реализовывать здесь алгоритм (который сейчас опишу) можно и массивами и векторами (во втором случае получится быстрее и экономичнее по используемой памяти).
Итак есть 4 номинала: 1 2 5 10
И есть К равное 3 (максимально взятое число монет из копилки).
Расмотрим сначало взятие 1 монеты из копилки. В данном случае суммы которые могут получится такие:
1 2 5 10 - назовем это первой строкой.
Теперь найдем 2 строку (какие суммы могут получится при взятии 2-х монет из копилки). Здесь нужно учитывать результаты из предыдущей строки (из первой). Итак перебираем возможные номиналы, которые можем взять. Берем первый номинал - это 1. Вторая строка пока получается такой:
2 3 6 11 - текущие значения второй строки (получились в результате сложения значения первой строки и рассматриваемого номинала).
Далее берем второй номинал - это 2. Теперь вторая строка получается такая:
2 3 4 6 7 11 12- текущие значения второй строки (получились в результате сложения значения первой строки и рассматриваемого номинала, если уже такие значения есть, то их не повторяем).
Далее берем третий номинал - это 5. Теперь вторая строка получается такая:
2 3 4 6 7 10 11 12 15- текущие значения второй строки (получились в результате сложения значения первой строки и рассматриваемого номинала, если уже такие значения есть, то их не повторяем).
Далее берем четвертый номинал - это 10. Теперь вторая строка получается такая:
2 3 4 6 7 10 11 12 15 20 - окончательные значения второй строки (получились в результате сложения значения первой строки и рассматриваемого номинала, если уже такие значения есть, то их не повторяем).
Т. е. вторая строка получилась:
2 3 4 6 7 10 11 12 15 20 - т.е. такие суммы могут получится если взять две монетки.
Теперь формируем третью строку (по тому же принципу):
Берем первый номинал - 1. Третья строка:
3 4 5 7 8 11 13 16 21
Берем второй номинал - 2. Третья строка:
3 4 5 6 7 8 9 11 12 13 14 16 17 21 22
Берем третий номинал - 5. Третья строка:
3 4 5 6 7 8 9 11 12 13 14 15 16 17 20 21 22 25
Берем четвертый номинал - 10. Третья строка:
3 4 5 6 7 8 9 11 12 13 14 15 16 17 20 21 22 25 30
Окончательные значения третьей строки:
3 4 5 6 7 8 9 11 12 13 14 15 16 17 20 21 22 25 30 - все возможные значения сумм. Их кол-во - 19 и есть ответ.
Сможете реализовать код или помочь?

1

Сообщение от valeriikozlov Сможете реализовать код или помочь?

попробую...
спасибо за помощь!
если не трудно --- вот

0