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 <rahul23111...@gmail.com> 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 algogeeks+unsubscr...@googlegroups.com.
