Coin Change Problem: minimum number of coins required to form sum S.

Question

Given an array of denominations and array Count , find minimum number of coins required to form sum S.

for example:

  coins[]={1,2,3};
  count[]={1,1,3};

i.e we have 1 coin of Rs 1 , 1 coin of Rs 2 , 3 coins of Rs 3.

Now if we input S = 6 then output should be 2 with possible combination : 3+3 = 6

Answer 1

Check this (I found this somewhere on Net and somehow link is lost), solved by the dynamic programming (obviously using recursion).

int coins [] = {1, 2, 3};
int cnt [] = {1, 1, 3};
const int INF = **********;
int memo [55][1005];

int   solve (int idx, int s)
{
    if (s == 0) return 0;
    if (s < 0 || idx < 0) return INF;
    if (memo [idx][s] != -1) return memo [idx][s];
    int ret = INF;
    for (int i = 0; i <= cnt [idx]; i++)
        ret = min (ret, i + solve (idx - 1, s - coins [idx] * i));  //Take i coins from coin [idx].
    return memo [idx][s] = ret;
}

int  main ()
{
    memset (memo, -1, sizeof (memo));
    int S = 6;
    int ret = solve (sizeof (coins) / sizeof (coins [0]) - 1, S);
    ret = ret >= INF ? -1 : ret;
    printf ("%d\n", ret);
}