private int[] _conins;

private void SortCoinsByAsc()
{
var count = _conins.Length;
for (int i = 0; i < count; i++)
{
for (int j = i + 1; j < count; j++)
{
if(_conins[i] > _conins[j])
{
var temp = _conins[i];
_conins[i] = _conins[j];
_conins[j] = temp;
}
}
}
}

public int[] GaveCoins(int sum)
{
var result = new List<int>();
var count = _conins.Length;
for (int i = count - 1; i >= 0; i--)
{
int coinCount;
do
{
coinCount = sum/_conins[i];
sum %= _conins[i];
for (int j = 0; j < coinCount; j++)
{
result.Add(_conins[i]);
}
if (sum == 0)
break;
} while (coinCount > 0);
}
return (sum == 0) ? result.ToArray() : null;
}

А если задать номиналы 8 и 3, а сумму 9?=)
Чето я не нашел тут блока, который может с этим разобраться.
Удачи с такой прогой.

#include <stdio.h>
#include <stdlib.h>

typedef struct {
int val;
int count;
} coin_t;

typedef struct {
int coin_index;
int count;
} change_t;

coin_t coins[] = {
// { 3, 5 },
{ 5, 20 },
{ 7, 20 },
};
const size_t coins_size = sizeof(coins) / sizeof(coin_t);

#define CHANGE_SIZE 100
change_t change[CHANGE_SIZE];
int change_index;

int calc_change(int money);
void print_change();

int main(int argc, char *argv[])
{
int money;
int r;

if (argc < 2) {
printf("Enter sum of money to change\n");
return -1;
}
money = (int)strtol(argv[1], NULL, 10);

r = calc_change(money);

if (r != 0) {
printf("Failed to change %u kop.\n", money);
} else {
int i;
printf("%u kops = ", money);
print_change();
}

return 0;
}

int calc_change(int money)
{
int money_changed = 0;
int ci = (int)coins_size - 1;

if (ci < 0) {
return -1;
}
change_index = 0;

while (1) {
// printf("money to change: %d, try current ci=%d..\n",
// money, ci);
if (ci < 0) {
/* back and repeat */
// printf("..back..\n");
change_index--;
if (change_index < 0) {
break; /* failure: can't change */
}

ci = change[change_index].coin_index;
if (ci > 0) {
change[change_index].count--;
coins[ci].count++;
money_changed -= coins[ci].val;
money += coins[ci].val;
// printf("..change item decresed, now: %d x %d kop.\n",
// change[change_index].count, coins[ci].val);
if (change[change_index].count > 0) {
change_index++;
}
ci--;
// continue;
} else {
int sum;
coins[ci].count += change[change_index].count;
sum = change[change_index].count * coins[ci].val;
change[change_index].count = 0;
money += sum;
money_changed -= sum;
// printf("current coin is last so descrese change for all coins of that value, "
// "request back ci=-1\n");
ci = -1;
continue; // back again, i.e. decrese higher-value-coin counter
}

}

// printf("ci=%d\n", ci);
// printf("change: ");
// print_change();

if (coins[ci].count > 0) {
int count = money / coins[ci].val; /* !!! val != 0 */
if (count > 0) {
int sum;
if (count > coins[ci].count) {
count = coins[ci].count;
}
coins[ci].count -= count;
change[change_index].count = count;
change[change_index].coin_index = ci;

sum = count * coins[ci].val;
money_changed += sum;
money -= sum;
// printf("..change item added: %d x %d kop.\n",
// count, coins[ci].val);
change_index++;

if (money == 0) {
break;
}
// ci--, continue
} // else ci--, continue
} // else ci--, continue

ci--;
} // while

return money == 0 ? 0 : -1;
}

void print_change()
{
int i;
for (i = 0; i < change_index; i++) {
if (i > 0) {
printf(" + ");
}
printf("%d x %dkop", change[i].count, coins[change[i].coin_index].val);
}
printf("\n");
}

..в догонку:
* программа требует один параметр - сумму для размена;
* условие чуть уточнено: добавлено ограничение на кол-во монет каждого номинала - так ближе к реальной жизни (можно убрать соотв проверки "if (coins[ci].count > 0) ==> if (1) ", тогда будет для исходного условия)
* для примера монеты и их кол-во заданы константами в массиве, длина массива под сдачу - не меньше длины массива, задающего монеты (чтобы не реализовывать ввод/вывод и динамическое выделение памяти = 100)

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

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

Вот, запутал, наверное с объяснением.. (если раскоменировать printf, то можно в корявом виде пронаблюдать логику)

...зыбыл важную деталь:
монеты в coins[] должны быть заданы в порядке возрастания номинала :)