Реализация алгоритмов

[mailjaffka]

Помогите реализовать жадный алгоритм и простой перебор (либо рекурсия) для задачи:
"Есть по 2 монеты достоинств а1,а2 ... аn. Можно ли этими монетами оплатить сумму S?"
Количество номиналов, сами номиналы и сумму вводим с клавиатуры

[mailjaffka]

реализовала только одним способом - похож чем-то на рюкзак

[mailjaffka]

нужно еще 2. не могу справиться

[k1r1ch]

Хм, интересно, динамику написали, а рекурсивный перебор не можете?!

[mailjaffka]

смогла, а про рекурсию не могу сообразить как именно.
например, если есть такой массив:
0 0 0
3 4 5
6 8 10
где, 3,4,5 - номиналы монет. вот как перебрать все сочетания (типа о о о, 0 0 5, 0 4 0, 0 4 10, 3 4 5 и т.д.)
помогите!!! Очень надо

[mailjaffka]

реализовала так свою тему
массив
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
3 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0
4 0 0 1 1 0 1 1 1 0 1 1 0 0 1 0
5

в общем, 1 стоит на том месте, где можно собрать данную сумму. а потом вывод ответа да/нет, если на месте 15 есть 1. в этом случае взяла сумму S=15