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[Sdenom[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[S_{i}]
has been expressed in terms of lookup[S_{j}]
where S_{j}
< S_{i},
the difference between S_{i}
and S_{j}
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 S_{i}
to S_{j}.
At S_{j},
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[Sdenom[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
d_{0}x
+ d_{1}y
+ d_{2}z
.... d_{i
}p
+ d_{m}q
= N
Where
N is the sum we need to count using the coins,
d_{i}
is i^{th}
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 d_{0}
= 2 and d_{1}
= 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 d_{i}
= N/d_{i}
So,
if we run a loop from 0 to N/d_{i}
for i^{th}
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 N_{i}
/ d_{i}
times where N_{i}
is the sum available at some stage and d_{i}
is the maximum
denomination available at that stage.
So
order of this algorithm is: O (
N_{1}
x N_{2}
x N_{3}
x .... N_{m}
/
d_{1}
x d_{2}
x d_{3}
x ... d_{m}
)
This
order reaches N^{m}/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 / d_{0}
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.
