@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]> 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].
>
--
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].
