В лоб - составить все возможные варианты набора определённой суммы, затем определить непересекающиеся группы наборов и для каждой группы рекурсивно перебирать все комбинации.
Скажем, номиналы 5, 4, 3, 2, необходимая сумма 8
Получаем наборы (5, 3), (4, 4), (4, 2, 2), (3, 3, 2), (2, 2, 2, 2).
Одна группа, в которую входят все наборы.
Номиналы 5, 4, 3, необходимая сумма 8
Получаем наборы (5, 3), (4, 4).
Две группы [(5, 3)] и [(4, 4)]
Для каждой группы.
Начиная с 0 смотрим, в цикле можем ли мы ещё раз взять первый набор. Если да, то рекурсивно смотрим, сколько раз можно набрать нужную сумму остальными наборами из группы из остатка монет. на каждом шаге цикла суммируем количество первых наборов и вернувшееся количество наборов из остатков. Ищем максимум этой суммы.
Пройдя по всем группам суммируем результаты, получаем общее число раз.