If you find a way to do that for more than a few coins I'd be interested in seeing it too. Don
On Thursday, May 15, 2014 3:00:04 PM UTC-4, atul007 wrote: > > @Don : i am intersted in DP bottom up approach with less time complexity. > solving it recursively is a simpler approach... > On 15 May 2014 22:25, "Don" <[email protected] <javascript:>> wrote: > >> How about this: >> >> const int N = 6; >> unsigned int coins[N] = {100,50,25,10,5,1}; >> unsigned int count[N] = {2, 1, 1, 5, 4, 10}; >> int best = 1000000000; >> >> int minCoins(int s, int f=0, int d=0) >> { >> if (d == 0) best = s; // It can never take more than s coins >> if (s < 1) return 0; // No coins required >> if (d >= best) return 100; // We've already used too many coins. >> int result=best; >> for(int i = f; i < N; ++i) // Don't regress >> { >> if (count[i]) // Only try coins which are available >> { >> if (coins[i] < s) // Try using this coin >> { >> --count[i]; >> int sum = 1 + minCoins(s-coins[i], i, d+1); >> if (sum < result) sum = result; >> if ((d == 0) && (sum < best)) best = sum; >> ++count[i]; >> } >> else if (coins[i] == s) return 1; // This coin is all we need >> } >> } >> return result; >> } >> >> int main() >> { >> int s; >> scanf("%d", &s); >> printf("The fewest coins to total to %d is %d\n", s, minCoins(s)); >> return 0; >> } >> >> On Thursday, May 15, 2014 1:35:12 AM UTC-4, atul007 wrote: >>> >>> Solving coin change problem with limited coins. >>> >>> Given an array of denominations and array Count , find minimum number of >>> coins required to form sum S. >>> >>> for eg: coins[]={1,2,3}; >>> count[]={1,1,3}; >>> i.e we have 1 coin of 1$ , 1 coin of 2$ , 3 coins of 3$. >>> >>> input S = 6 >>> output = 2 >>> >>> possible combination : 3+3 = 6 >>> >> -- >> 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] <javascript:>. >> > -- 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].
