top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

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

+1 vote
431 views

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

posted Jun 15, 2014 by anonymous

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

0 votes

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);
}
answer Jun 16, 2014 by Salil Agrawal
Similar Questions
+2 votes

Given an infinite supply of coins of denominations {20,10,5,1}, find out total number of way to make change of given amount - 'n'?
For example, if given amount is 20, there are 10 ways to make this change as shown below -
(1 of 20),(1 of 10 + 2 of 5),(1 of 10 + 1 of 5 + 5 of 1),(1 of 10 + 10 of 1), (2 of 10), (1 of 5 + 15 of 1),(2 of 5 + 10 of 1),(3 of 5 + 5 of 1),(4 of 5),(20 of 1)

If the amount given is 0 then the total number of ways to make change is 1 - using 0 coins of every given denomination.

+5 votes

Given 2 strings s1, s2 and s1 is equal to s2 if they are lexicographically sorted, Find minimum number of swaps required to transform s1 to s2?

Swap Definition:
Problem 1 : we can transform index i with i+1 where 0<=i< s1.length()-1
Problem 2 : we can transform index i with i+1 where 0<=i< s1.length()-1 and other operation we can swap first character of string with last

example: s1="abc", s2="cba"
In problem1 3 swaps required abc ---> bac ---> bca ---> cba
In problem2 1 swaps required abc ---> cba [swap first and last element]

+3 votes

Standard Coin denomination problem is as follows

coin set = {1,2,5,10 ... } - each coin count is unlimited
find count of possible combinations of coins to create N Rs

This problem can either be done using backtracking or dynamic programming

Now My requirement added a factor where max count of each coin is given e.g.

{ (1, 10), (2, 5), (5, 4), (10, 100) } where (n,m) denotes m coins are of each n Rupees.

This can be done using backtracking by an addition check while inserting element to stack but this takes exponential time. Can somebody provides solution using dynamic programming ?

thanks in advance..

+8 votes

Divide the array in two subarrays of n/2 sizes each such that the difference of the sum of two subsets is as minimum as possible. If n is even, then sizes of two subarray must be n/2 and if n is odd, then size of one subarray must be (n-1)/2 and size of other subset must be (n+1)/2.

...