Размен монет на С++

[BvaKell]

Есть неограниченный набор монет разного достоинства (количество различных достоинств задается на момент старта алгоритма). Требуется разменять заданное число N этими монетами, найти наименьшее количество монет, которые в сумме дают величину N, или указать, что задача не имеет решения.

Помогите пожалуйста, в программировании новичок, но требуется срочно сдать...

[Abstraction]

Помогите пожалуйста, в программировании новичок, но требуется срочно сдать...

Плохо. Это не очень лёгкая задача.
Ищите по ключевым словам "поиск в ширину", BFS. Если N не очень велико, можно создать массив из N значений и последовательно его заполнять.

[BvaKell]

Мне подсказку дали использовать жадный алгоритм, язык программирования может быть с++, питон, с#

[Abstraction]

Мне подсказку дали использовать жадный алгоритм

Не понял?..
Пусть монеты 1, 5, 7. Берём N=11. Жадный алгоритм даёт разбиение 11=7+1+1+1+1, 5 слагаемых. Оптимальное решение 11=5+5+1, 3 слагаемых.

[Smitt&Wesson]

Это очень лёгкая задача. Если по условию, начинаем с бо'льшего и заканчиваем наименьшим.
Например - разменять 125 р 25 к.
Имеются купюры (монеты):
100 р
50 р
10 р
1 р
50 к
10 к
1 к

Берём наибольшее 100 р и вычитаем его из размениваемого числа.
125.25 - 100 = 25.25
Берём следующее "разменное число":
25.25 - 50 = -24.75
Результат отрицательный - отбрасываем
25.25 - (10 +10 (цикл)) = 5.25
5.25-10 = -4,75 - отбрасываем
5.25 - (1 + 5 ()в цикле) = 0.25
Ну и так далее. Предложите иной алгоритм.

Есть другая задача, имеющая более практическое значение.
В купюрообменнике имеются купюры разного достоинства, но их количество ограниченно и не равно. Придумать такой алгоритм, что-бы при любом, количестве вероятно обмениваемых купюр, ни одна ячейка не опустела, меньше чем на собственный номинал.

[BvaKell]

Требуется разменять заданное число N этими монетами, найти наименьшее количество монет, которые в сумме дают величину N, или указать, что задача не имеет решения.
при использовании жадного, можно указать для некоторых случаев, что задача не решается...Да и с ним код попроще будет.Но проблема остается, написать мне его трудно, мне бы сам код,если не трудно...

[Smitt&Wesson]

BvaKell, тук-тук-тук. Вы нас слышите? Я расписал алгоритм, а Вам, что по-башке, что по-лбу. Работаем или платим за решение. Вопросы есть?
- нет! Вы на программиста нахрена учитесь?, Что-бы студням бесплатно задачки решать? А не херово-ли будет?

[Abstraction]

Ну и так далее. Предложите иной алгоритм.

Приведён контрпример. В Вашем алгоритме есть контрпример покруче: N=12, набор 3,6,7. Вычитаем 7, вычитаем 3, облом. А размен существует.
Если нам скармливают массив пар достоинств монеты и её количества, причём изначально количества заполнены нулями, а достоинства упорядочены по убыванию и завершаются нулём, такой код всегда найдёт размен, если он существует:

bool FindChange(int N, int*const* coins){
  if(N==0) return true;
  if(**coins==0) return false;

  if(N < **coins) return FindChange(N, coins+1);
  if(FindChange(N-**coins, coins)){
    coins[0][1]++;
    return true;
  }
  return FindChange(N, coins+1);
}

[BvaKell]

Сделал код на питоне, только проблема в том. что пользователь должен сам вводить кол-во монет определенного достоинтсва, как можно сделать. чтобы оно было неограниченным?
def Razmen(sm, mas, mon):
if not mas:
return False
for i in range(len(mas)):
n = sum(mon) + mas[i]
if n > sm:
continue
elif n < sm:
mon.append(mas[i])
m = Razmen(sm, mas[i+1: ], mon)
if not m:
mon.pop()
else:
mon.append(mas[i])
return True

if __name__ == "__main__":
massiv=[]
num = int(input('Kol-vo Dostoinstv: '))
summa = int(input('Summa: '))
n=0
while(n<num):
massiv.append(int(input()))
n=n+1
print (len(massiv))
massiv.sort(reverse=True)
mon = []
kol=len(massiv)
k=0
Razmen(summa, massiv, mon)
kol=kol-len(mon)
k=k+1
print ('Moneti s d-vom: ', mon)
print ('Itogovaya summa: ', sum(mon))
print ("")