This is a DP approach which is good if you need to perform the
operation for a large number of values of S.
For many combinations of coins, a greedy approach will work, but there
are combinations of coins where the greedy approach does not work. The
method below will work for any set of available coins.
Don
#include <stdio.h>
int main()
{
const int numCoins = 6;
const int maxS = 10000;
int coins[numCoins] = {1,5,10,25,50,100}; // You can change this
if you want different sets of coins
int min[maxS];
int i, j;
for(i = 1; i < maxS; ++i) min[i] = 1000000000;
min[0] = 0;
for(i = 0; i < maxS; ++i)
for(j = 0; j < numCoins; ++j)
if ((i+coins[j] < maxS) && (coins[i+coins[j]] > coins[i]))
coins[i+coins[j]] = coins[i] + 1;
// Now coins[S] is the minimum number of coins required to sum to S
}
On May 18, 5:22 pm, rahul sharma <[email protected]> wrote:
> Minimum of coins to sum s
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
