@Don: The greedy algorithm will work for any S if the set of coins
satisfies the following conditions:
1. There is a one-unit coin.
2. Each coin has value at least twice the value of the next less valuable
coin.
E.g., U.S. coin system has values 1, 5, 10, 25, 50, and 100 cents. The
conditions above are satisfied, so the greedy algorithm works.
E.g., The greedy algorithm does not work with a coin system with 1, 4, and
5 unit coins. 8 units can be made with two 4-unit coins, but the greedy
algorithm uses 5, 1, 1, and 1.
Dave
On Tuesday, May 28, 2013 9:55:01 AM UTC-5, Don wrote:
> 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].
