Make delicious recipes!

Find minimum no of coins required to compute sum S


Suppose we knew the minimum no of coins required to form sum 0 to S for coins 0 to k, then introduction of another coin k+1 should change all minimum coins from 0 to S as follows:

If minCoins[S] < 1 + minCoins[S-(k+1)], change the minCoins count at Sum S


This can be expressed as:

int findMinCoins (int Sum, int denoms [])
{
    int lookup[Sum+1] = {0};

    for (int i=0; i<denoms.length; i++)
    {
        for (int S=1; S<=Sum; S++)
        {
            if (S > denoms[i])
            {
                int minCoinsWithNewCoin = lookup[S-denom[i]] + 1;
                if (minCoinsWithNewCoin < lookup[S] || lookup[S]==0)
                    lookup[S] = minCoinsWithNewCoin;
            }
        }
    }

    return lookup[Sum];
}



Find min number of coins and also print the denominations in solution


Since lookup[Si] has been expressed in terms of lookup[Sj] where Sj < Si, the difference between Si and Sj gives us the denomination of one of the coin.

So, if store the first denomination required at each stage, then we can use it to get from Si to Sj. At Sj, we can check the denomination stored there to go further below and so on.


int findMinCoins (int Sum, int denoms [])
{
    int lookup[Sum+1] = {0};
    int biggestDenomAtSumK[Sum+1] = {-1};

    for (int i=0; i<denoms.length; i++)
    {
        for (int S=1; S<=Sum; S++)
        {
            if (S > denoms[i])
            {
                int minCoinsWithNewCoin = lookup[S-denom[i]] + 1;
                if (minCoinsWithNewCoin < lookup[S] || lookup[S]==0)
                {
                    lookup[S] = minCoinsWithNewCoin;
                    biggestDenomAtSumK[S] = denom[i];
                }
            }
        }
    }

    int S=Sum;
    while (S > 0)
    {
        System.out.println (biggestDenomAtSumK[S]);
        S = S - biggestDenomAtSumK[S];
    }

    return lookup[Sum];
}

Another way of looking at this problem is that we can think each combination of coins as a solution to the equation

d0x + d1y + d2z .... di p + dmq = N

Where N is the sum we need to count using the coins,

di is ith denomination in the coins’ denomination array.

and x, y, z ... p, q are the coefficients whose different values provide us all the solutions to this problem


For example, if N = 10 and d0 = 2 and d1 = 4, then equation formed would be:

2x + 4y = 10 (remember the staircase problem discussed above?)


It can be solved with following values:

x=1, y=2

x=3, y=1


Also, maximum number of coins that can be used for a particular denomination di = N/di

So, if we run a loop from 0 to N/di for ith denomination and consider all values in that range, then we can consider the remaining denominations for other values.

Continuing in this fashion, we can find both the solutions - minimum no of coins and maximum no of ways.



The above is basically application of greedy algorithm, if we sort the denoms[] in ascending order before passing to this function. It will consider the maximum possible count of highest denomination first and then try to figure out if a solution exists with other denominations. If yes, it returns the count of coins used in that solution, else it reduces the count of highest denomination by 1 and tries again.

So at every level, the loop executes Ni / di times where Ni is the sum available at some stage and di is the maximum denomination available at that stage.

So order of this algorithm is: O ( N1 x N2 x N3 x .... Nm / d1 x d2 x d3 x ... dm )

This order reaches Nm/m! in the worst case where all denominations are equal.

However, for such a case we can optimize even further by obtaining the solution in one step = N / d0


The above is very helpful in finding whether a solution exists or not.

It can be modified a little bit to find maximum no of ways also.


Also, a lookup table [N][denomLen] can be inserted to introduce DP into this for further optimization.




Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal